Prefix sums

A prefix sumprefix sumAn array where each element stores the cumulative sum of all elements up to that index, enabling O(1) range-sum queries.In the glossary array precomputes cumulative totals so you can answer "what is the sum from index i to j?" in constant time. Instead of looping through all values in the range, you subtract two prefix sums.

Building a prefix sum array

Imagine you have an array of daily sales:

sales = [10, 20, 15, 30, 25]

A prefix sum array stores the cumulative total up to each index:

prefix = [0, 10, 30, 45, 75, 100]

prefix[0] is 0 (no elements before the array). prefix[1] is 10 (sum of sales[0]). prefix[2] is 30 (sum of sales[0] and sales[1]). And so on.

To build this, start with zero and add each element:

1sales = [10, 20, 15, 30, 25]2prefix = [0]3for s in sales:4    prefix.append(prefix[-1] + s)5print(prefix)

The output is:

[0, 10, 30, 45, 75, 100]

Answering range queries

Now, to find the sum from index 1 to 3 (inclusive), use the formula: prefix[j+1] - prefix[i], where i and j are the start and end indices.

Sum from index 1 to 3: prefix[4] - prefix[1] = 75 - 10 = 65. The values are sales[1] + sales[2] + sales[3] = 20 + 15 + 30 = 65. Correct.

With preprocessing, each query runs in O(1) time. If you have 100,000 sales values and 10,000 range queries, preprocessing saves millions of operations.

Prefix and suffix maximums

You can precompute prefix maximums the same way. prefix_max[i] stores the largest value from index 0 to i.

1sales = [10, 20, 15, 30, 25]2prefix_max = [0]3for s in sales:4    prefix_max.append(max(prefix_max[-1], s))5print(prefix_max)

The output is:

[0, 10, 20, 20, 30, 30]

Building suffix_max works the same way, from the right: suffix_max[i] stores the largest value from index i to the end.

1sales = [10, 20, 15, 30, 25]2suffix_max = [0]3for s in reversed(sales):4    suffix_max.append(max(suffix_max[-1], s))5suffix_max.reverse()

Unlike prefix sums, this pair does not answer an arbitrary middle range like "the maximum from index 1 to 3" on its own. Two prefix sums combine into any range sum because subtraction undoes addition. No operation undoes a maximum, so a prefix max and a suffix max cannot be combined the same way. What they do answer directly is a range anchored at one end: prefix_max[i] is the best value anywhere in sales[0:i], and suffix_max[i] is the best value anywhere in sales[i:].

That pairing is exactly what a problem like "buy on one day, sell on a later day, maximize the profit" needs. For each day i starting from day 1, prefix_max[i] is the highest price on any day before i (indices 0 through i - 1). So sales[i] - prefix_max[i] is the profit from selling on day i after buying at the best earlier price, and comparing that value across every day from 1 onward finds the best sale. Reading the array from the opposite end with suffix_max answers the mirror question: the best day to sell after a given day to buy. A single prefix max or suffix max only ever covers one direction.

The same technique applies to range minimums and other associative operations, as long as you keep in mind which end each array covers.

When to build a prefix sum array

Not every problem needs preprocessing. If you have only a few queries, looping through the range each time is simpler and often faster. But if the problem has many queries, or if the data is large, preprocessing pays off immediately.

The decision is usually clear from the problem statement. If it says "process Q queries" and Q is large (thousands or more), reach for prefix sums.

2D prefix sums

On a 2D grid, a prefix sum array lets you query the sum of any rectangular region in O(1) time.

A grid might represent pixels or cell values. To build a 2D prefix sum:

1grid = [2    [1, 2, 3],3    [4, 5, 6],4    [7, 8, 9]5]6
7rows, cols = len(grid), len(grid[0])8prefix = [[0] * (cols + 1) for _ in range(rows + 1)]9
10for i in range(rows):11    for j in range(cols):12        prefix[i+1][j+1] = (13            grid[i][j]14            + prefix[i][j+1]15            + prefix[i+1][j]16            - prefix[i][j]17        )

The formula includes the cell value, adds the sum above and to the left, and subtracts the overlap (counted twice).

To query the sum of a rectangle from (r1, c1) to (r2, c2):

1prefix = [[0, 0, 0, 0], [0, 1, 3, 6], [0, 5, 12, 21], [0, 12, 27, 45]]2r1, c1, r2, c2 = 0, 0, 1, 13rect_sum = (4    prefix[r2+1][c2+1]5    - prefix[r1][c2+1]6    - prefix[r2+1][c1]7    + prefix[r1][c1]8)

This is the inclusion-exclusion principle applied to a grid. The top-left corner (r1, c1) is included. The cell at (r1-1, c1) and above are excluded. The cell at (r1, c1-1) and to the left are excluded. But the overlap at (r1-1, c1-1) was excluded twice, so add it back once.

A second example: cumulative game scores

Suppose you track your score round by round. A query asks "what were my total points from round i to round j?" A prefix sum array avoids recalculating the sum from scratch for each query.

1points = [10, 5, 8, 12, 3, 7]2queries = [(0, 2), (2, 5), (1, 3)]3
4# Build prefix sum5prefix = [0]6for p in points:7    prefix.append(prefix[-1] + p)8
9for start, end in queries:10    total = prefix[end + 1] - prefix[start]11    print(total)

The output would be 23, 30, and 25 for the three queries. Round 0 to 2 sums to 10 + 5 + 8 = 23. Without prefix sums, each query loops through the range; with it, each query is O(1).

Common mistakes with prefix sums

One error is off-by-one indexing. The formula for a range sum is prefix[j+1] - prefix[i], where i and j are inclusive indices in the original array. It is easy to mix up which indices to use. Always verify with a small example first.

Another mistake is using the original array inside a loop after building the prefix sum. Once you have the prefix array, you no longer need the original data for range queries. If you need both, keep both, but do not confuse them.

A third mistake is forgetting that prefix sums are only efficient if you build once and query many times. If the data changes frequently, the cost of rebuilding the prefix array for each change outweighs the savings from fast queries. In those cases, a segment tree or other dynamic structure is better.

When to use prefix sums

Use prefix sums when you have an array or grid and many range queries. The upfront cost of building the prefix array is paid off by the speed of answering queries.

If you have only one query, a direct loop is faster. If you have millions of queries, preprocessing is essential. Most competitive programming problems that mention "sum over a range" are hinting at prefix sums.

Prefix sums also work for other associative operations like minimum, maximum, and bitwise OR. The underlying principle is the same: precompute a cumulative result and use it to answer range queries in constant time.