Prefix Sums

Pay once up front so every range question afterwards is free.

The idea

A prefix sum array holds, at each position, the total of everything up to and including it. Build it once in O(n), and the sum of any range [lo, hi] becomes a single subtraction:

sum(lo, hi) = prefix[hi] - prefix[lo - 1]

That is the whole technique. Its value is entirely in the trade it makes: one linear pass up front turns every subsequent range query from O(n) into O(1). If you ask one question it is a waste; if you ask many it is transformative.

The same idea generalises past addition. Any operation with an inverse works — prefix XOR answers range XOR, prefix products answer range products if you are careful about zeros. Operations without an inverse, like minimum, do not work this way and need a sparse table or a segment tree instead.

The mirror image is the difference array: instead of querying ranges cheaply, you update them cheaply. Add v at lo and subtract it after hi, then one prefix pass at the end applies every range update at once.

In two dimensions the same subtraction becomes inclusion-exclusion over four corners, which is how you answer submatrix sums in constant time.

Walkthrough

The array becomes its own prefix table in one pass, then the answer for [1, 3] is one subtraction. Watch each cell absorb everything to its left.

What it costs

time: O(n) to build, O(1) per range query
space: O(n), or O(1) if you overwrite the input as here

The break-even point is one query: below that, summing the range directly is cheaper. Above it, the build cost is amortised away immediately.

When to reach for it

Many range-sum questions over an array that does not change.
You need "does a subarray with sum k exist?" — prefix sums plus a hash map answers it in one pass.
Range updates rather than range queries, which is the difference array.
Submatrix sums, where the same subtraction becomes four corners.

Rather than the obvious alternative

Recomputing the sum each query

O(n) per query. Fine for one; catastrophic for many, which is exactly when this technique is offered.

A sliding window

A window handles contiguous ranges that move, and handles them in O(1) space. Prefer it when the range slides; prefer prefix sums when queries land anywhere, in any order.

A segment tree or Fenwick tree

Necessary once the underlying array *changes* between queries — a prefix array must be rebuilt in O(n) after any update. Also the answer for min or max, which have no inverse to subtract.

How to spot it

The problem asks for sums of many different subarrays.
It says "subarray sum equals k", which is prefix sums plus a hash map.
The array is fixed and the queries are numerous.
You are applying many range updates and only need the result at the end.

Where it goes wrong

The off-by-one at the lower bound

`prefix[hi] - prefix[lo]` excludes `nums[lo]`. You want `prefix[lo - 1]`, and `lo = 0` needs its own case — which is why many implementations pad the array with a leading zero.

Building it when the array will change

One update invalidates every entry after it. If updates are interleaved with queries, this is the wrong structure.

Overflow on large inputs

A prefix sum is by definition the largest number in the problem. In fixed-width languages this is where it overflows, not in the individual elements.

Try it

Two short checks. They run the same way the practice problems do — write the function, press Run.

Turn nums into its own prefix-sum array in place and return it.

Or press ⌘↩

Tests

4 cases, 1 hidden

call	type	expected	result
buildPrefix([3,1,4])	typical	[3,4,8]	—
buildPrefix([2,-1,3])	with negatives	[2,1,4]	—
buildPrefix([9])	single element	[9]	—
withheld	hidden	withheld	—

Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.

Hints

Stuck? Hints open one at a time, each giving a little more away.

2 hints left

Practise it

Subarray Sum Equals Kmedium