Learn how to precompute cumulative sums to answer range queries in O(1) instead of O(n).

Prefix Sum

A prefix sum array stores the cumulative sum of all elements up to each index. Once built, it answers any range sum query in O(1) — no matter how many queries you need.

The problem it solves

Problem: Given an array, answer many queries — each asking for the sum of elements between index l and r.

Without prefix sum — O(n) per query:

# for each query, loop through the range
total = sum(arr[l:r+1])   # O(n) every time

For 1000 queries on an array of 1000 elements — that is 1,000,000 operations.

With prefix sum — O(1) per query after O(n) preprocessing:

# build once — O(n)
# answer each query — O(1)

Prefix Sumbuild O(n) · query O(1)

Input array — arr

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Prefix sum array — prefix[i] = sum of arr[0..i-1]

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

prefix_sum.py

def build_prefix(arr):

prefix = [0] # extra 0 at start

for i, val in enumerate(arr):

prefix.append(prefix[-1] + val)

def range_sum(l, r):

return prefix[r+1] - prefix[l]

Build prefix sum for [3, 1, 4, 1, 5, 9, 2, 6]

step 0/16

Building the prefix sum array

def build_prefix_sum(arr):
    n = len(arr)
    prefix = [0] * (n + 1)   # one extra element at index 0

    for i in range(n):
        prefix[i + 1] = prefix[i] + arr[i]

    return prefix


arr = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = build_prefix_sum(arr)

# prefix[i] = sum of arr[0..i-1]
# prefix[0] = 0
# prefix[1] = 3
# prefix[2] = 4   (3+1)
# prefix[3] = 8   (3+1+4)
# ...

Answering range queries in O(1)

def range_sum(prefix, l, r):
    # sum of arr[l..r] = prefix[r+1] - prefix[l]
    return prefix[r + 1] - prefix[l]


arr = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = build_prefix_sum(arr)

print(range_sum(prefix, 0, 2))   # 8  → 3+1+4
print(range_sum(prefix, 2, 5))   # 19 → 4+1+5+9
print(range_sum(prefix, 1, 6))   # 22 → 1+4+1+5+9+2

Why it works:

sum(arr[l..r]) = sum(arr[0..r]) - sum(arr[0..l-1])
               = prefix[r+1] - prefix[l]

The prefix array stores sums from the start. To get a range sum, subtract the part you do not want.

A real example — count subarrays with sum equal to k

One of the most common interview problems. Prefix sum makes it O(n):

from collections import defaultdict

def subarray_sum_equals_k(arr, k):
    count = 0
    current_sum = 0
    seen = defaultdict(int)
    seen[0] = 1   # empty prefix

    for num in arr:
        current_sum += num

        # if (current_sum - k) was seen before
        # there exists a subarray ending here with sum = k
        if current_sum - k in seen:
            count += seen[current_sum - k]

        seen[current_sum] += 1

    return count


arr = [1, 2, 3, 2, 1]
print(subarray_sum_equals_k(arr, 3))   # 3
# subarrays: [1,2], [3], [2,1]

2D prefix sum

The same idea extends to 2D grids — precompute cumulative sums for rectangles:

def build_2d_prefix(grid):
    rows = len(grid)
    cols = len(grid[0])
    prefix = [[0] * (cols + 1) for _ in range(rows + 1)]

    for r in range(rows):
        for c in range(cols):
            prefix[r+1][c+1] = (
                grid[r][c]
                + prefix[r][c+1]
                + prefix[r+1][c]
                - prefix[r][c]
            )

    return prefix


def range_sum_2d(prefix, r1, c1, r2, c2):
    return (
        prefix[r2+1][c2+1]
        - prefix[r1][c2+1]
        - prefix[r2+1][c1]
        + prefix[r1][c1]
    )

When to use prefix sum

Signal	Use prefix sum
Multiple range sum queries	Yes
"Sum between index l and r"	Yes
Subarray sum equals k	Yes
Running total needed	Yes
Single query only	No — just loop
Non-additive operations (max, min)	No — use segment tree

The key insight — if you are going to answer the same type of range query many times, pay O(n) once to build the prefix array, then answer every future query in O(1). The more queries, the bigger the win.

Complexity

Operation	Time	Space
Build prefix array	O(n)	O(n)
Single range query	O(1)	O(1)
n queries without prefix	O(n²)	O(1)
n queries with prefix	O(n) total	O(n)

Prefix Sum

On this page