Prefix sums

The idea

A range sum is the difference of two running totals

The sum of positions 1 to 3 of a list is (the sum of positions 0 to 3) minus (the sum of position 0). So if you have stored, for every position, the total of everything before it, any range sum is one subtraction.

That stored list is the prefix sum array: prefix[i] is the sum of the first i items, with prefix[0] = 0. It has one more cell than the list, which keeps the formula free of special cases: the sum of positions a to b is prefix[b + 1] − prefix[a].

The rule

Build prefix sums once in O(n), and the sum of any range costs O(1): prefix[b + 1] − prefix[a]. A run ending at j sums to k exactly when some earlier running total equals the total at j minus k.

Spotting it

Range sums, and runs with an exact sum

Many questions about the sum of a range

Build once, answer each in O(1)

Count subarrays whose sum is exactly k

A hash map counts earlier running totals

Negative numbers, where a sliding window can't shrink safely

Prefix sums don't care about signs

Equal numbers of two kinds in a run (count +1 and −1)

Equal running totals mark a balanced run

Basic

Answer range-sum questions in O(1) each

Build the running totals, then answer two questions about ranges, each with a single subtraction.

Without the prefix array, each question would add up its whole range: O(n) per question. With it, q questions cost O(n + q).

Medium

Count the subarrays that sum to k

Now flip the formula. A run ending at position j sums to k when prefix[j + 1] − prefix[i] = k for some earlier i, that is, when some earlier running total equals the current total minus k. So walk the list once, keep a hash map from each running total seen so far to how many times it was seen, and at every position look up total − k.

The map starts with {0: 1}: the empty run before the first item, so that runs starting at position 0 are counted. The list includes a −1, which would break a sliding window; prefix sums don't mind.

Hard

When the sum you want is zero, remember where each total first appeared

Turn every 0 into −1 and the question "as many 0s as 1s" becomes "adds up to 0". A run adds up to 0 exactly when the running total at its end equals the total just before its start. So keep, for each total, the first position it appeared at; the longest run is the biggest gap between two equal totals.

The template

The two shapes to reuse

Range sums

1prefix ← [0]
2for i from 0 to length of xs − 1
3 append prefix[i] + xs[i] to prefix
4-- the sum of positions a to b is prefix[b + 1] − prefix[a]

Runs with an exact sum

1seen ← {}; seen[0] ← 1
2total ← 0
3for each x in xs
4 total ← total + x
5 if total − k in seen
6 count ← count + seen[total − k]
7 add 1 to seen[total]

Traps

Where prefix-sum solutions go wrong

Off by one

The prefix array has n + 1 cells; the range a … b uses prefix[b + 1], not prefix[b].

Forgetting the empty run

Without seen[0] ← 1, runs that start at the first item are missed.

Updating the map too early

Look up total − k before adding the current total, or with k = 0 every position counts the empty run ending at itself.

Changing data

Prefix sums suit lists that don't change. If items are updated between questions, every later total changes; Segment & Fenwick trees handle that.

Check yourself

3 questions

1. xs = [3, 2, 4, 1] gives prefix = [0, 3, 5, 9, 10]. What is the sum of positions 1 to 2?

2. Counting runs that sum to k, why does the map of earlier totals start as {0: 1}?

3. A list has negative numbers and you must count the runs that sum to k. Why prefix sums and not a sliding window?

Takeaways

Remember this

prefix[i] is the sum of the first i items; the sum of positions a to b is prefix[b + 1] − prefix[a].
Build once in O(n), then answer any number of range sums in O(1) each.
To count runs summing to k, look up total − k in a hash map of earlier totals, starting with {0: 1}; negatives are fine.

Practice

Now solve some yourself

Mixed with topics you have practiced 0 unlocked

2 more once you have practiced Hash tables & maps, Monotonic stack & queue. Play one of its examples to the end and solve one of its problems to unlock them.

Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.