Prefix Sum

A prefix sum is a running total: pre[i] is the sum of the first i elements. Build that array once in O(n), and the sum of any range becomes a subtraction.

That is a small idea with a large reach. It turns repeated range queries from O(n) each into O(1) each, and — paired with a hash map — it turns a whole class of “find the subarray that…” problems from quadratic into a single pass.

The definition, and the leading zero#

pre[0] = 0                          // sum of nothing
for i = 0 .. n - 1:
    pre[i + 1] = pre[i] + a[i]

// sum of a[l .. r-1]  ==  pre[r] - pre[l]

The array has n + 1 entries, not n, and the extra one at the front is doing real work. With pre[0] = 0 defined, the sum of a range starting at index 0 needs no special case — it is just pre[r] - pre[0]. Drop the leading zero and every formula acquires an if l == 0 branch, which is where the off-by-one errors live.

Note the range convention: pre[r] - pre[l] gives the half-open range [l, r). If your problem states ranges inclusively, it is pre[r + 1] - pre[l]. Pick one and write it down — this is the same discipline that the binary search article is built on, and it matters here for the same reason.

The trade is explicit: O(n) memory and a one-off O(n) pass, in exchange for O(1) per query. With one query that is a loss. With many, it is the whole game.

Differences of totals#

Here is the step that makes prefix sums more than a convenience. Rearrange the formula:

A subarray sums to k exactly when two prefix totals differ by k.

So instead of looking for subarrays, look for pairs of totals — and finding a partner for a known value is what a hash map does in O(1). This is the complement trick applied to running totals rather than to elements.

Watch what is never done: no subarray is ever added up. Each step computes one running total, subtracts k from it, and asks the map whether that number has been seen. A hit is not a candidate to verify — it is a proven answer, because the difference of the two totals is the sum of the stretch between them.

seen = { 0: 1 }              // the empty prefix, seen once
run = 0
count = 0

for x in nums:
    run = run + x
    count = count + seen.get(run - k, 0)     // every total that pairs with this one
    seen[run] = seen.get(run, 0) + 1

return count

Three details, each of which is a real bug when missed:

• Seed the map with {0: 1}. That entry represents the empty prefix, and it is what allows a subarray starting at index 0 to be counted. Without it, every such answer is silently dropped.
• Add to the count before inserting the current total. Otherwise a k of 0 lets an element pair with itself.
• Store counts, not just presence. The same total can occur many times, and each occurrence is a distinct subarray. A set gives you the wrong answer whenever it can be more than one.

Two variants come from changing what the map stores:

• Counting subarrays — store how many times each total has occurred, as above.
• Finding the longest such subarray — store the earliest index at which each total occurred, and never overwrite it. Earliest gives the widest span.

The special case k = 0 is worth naming, because it appears in disguise: two equal prefix totals mean the stretch between them sums to zero. Problems about equal counts of two things usually reduce to this by mapping one to +1 and the other to −1.

Prefix and suffix together#

Some problems need what lies on both sides of each position. Product of Array Except Self is the standard one — the answer at i is everything before it times everything after it — and it is solved with the same idea run twice, once in each direction. The Miscellaneous article steps through it, including the trick of using the output array to hold the first sweep so no second array is needed.

Maximum Subarray has a prefix-sum reading too, and it is worth seeing even though Kadane’s is what you would write. The best subarray ending at i is pre[i+1] minus the smallest prefix total before it — so scanning while tracking the minimum total so far gives the answer in one pass. That is exactly the shape of Best Time to Buy and Sell Stock, which is not a coincidence: both are “largest difference, later minus earlier”, and both are greedy scans over a running quantity.

The inverse: difference arrays#

Prefix sums make range queries cheap on a fixed array. The mirror image makes range updates cheap, and it is rarely taught despite being just as simple.

To add v to every element of [l, r], do not touch the range. Record the change at its two boundaries:

diff[l]     += v
diff[r + 1] -= v

Each update is O(1) no matter how wide the range. After all the updates, one prefix-sum pass over diff materialises the final array — the +v switches on at l and the −v cancels it at r + 1.

This is what turns “apply m range updates to an array of n” from O(n·m) into O(n + m). The same idea underlies the sweep-line counting in intervals: a +1 at each start and a −1 at each end, then a running total. That is a difference array in all but name.

Two dimensions#

Prefix sums extend to a grid, where pre[r][c] is the sum of the rectangle from the origin to (r, c). The query needs inclusion-exclusion, because the two overlapping rectangles you subtract share a corner:

// sum of the rectangle (r1, c1) .. (r2, c2), inclusive
total = pre[r2+1][c2+1]
      - pre[r1][c2+1]          // strip above
      - pre[r2+1][c1]          // strip to the left
      + pre[r1][c1]            // that corner was subtracted twice

The + pre[r1][c1] is the part people forget, and the way to remember it is not the formula but the picture: subtracting both strips removes their overlap twice, so it has to be added back once.

When it does not work#

Prefix sums rely on the operation being invertible — you must be able to recover a range from two accumulated values. That holds for sum and for XOR (which is its own inverse), and it does not hold for minimum or maximum: knowing the minimum of the first j elements and of the first i tells you nothing about the minimum between them. Range minimum queries need a sparse table or a segment tree instead.

The other limit is mutation. A prefix array is a snapshot; change one element and every total after it is wrong, so an update costs O(n) to repair. If the problem interleaves updates with queries, you want a Fenwick tree or a segment tree, both of which do updates and queries in O(log n).

And the comparison worth having ready, because the two techniques look interchangeable and are not:

A sliding window needs validity to be monotonic as the window grows, which negative numbers destroy. Prefix sums do not care about signs. For “subarray summing to exactly k” over values that may be negative, the window is unsound and the prefix-sum map is the correct tool.

Recognising it#

Reach for prefix sums when:

• The problem asks about the sum of a range, and especially when it asks many times.
• You need to count or find subarrays with a given sum, and a nested loop over starts and ends is the obvious approach.
• The input contains negative numbers and the question is about contiguous sums — that rules out a sliding window and rules this in.
• The problem applies many range updates before reading anything. That is a difference array.
• Something must be computed for every position in terms of everything on one side of it — the prefix and suffix sweep.

And the check: is the accumulating operation invertible, and does the array stay still while you query it? If either answer is no, you need a tree.

Summary#

One pass builds the totals; after that every range is a subtraction. Keep the leading zero and decide your interval convention before writing the formula. The idea that carries furthest is not the array but the rearrangement: a subarray sums to k exactly when two totals differ by k — which turns a search over subarrays into a lookup for a number, and a quadratic scan into a single pass. Run it in both directions for prefix-and-suffix problems, run it backwards as a difference array for range updates, and reach for a tree the moment the data starts changing underneath you.