Prefix sums are the cheapest big win in the arrays track. One pass of preparation converts every range-sum query from linear to constant, and the same idea in a slightly different costume solves a whole family of subarray-counting problems.
The construction
Use the length n+1 version with a leading zero. It removes every special case for l = 0, and essentially all prefix-sum off-by-one bugs come from trying to save that one slot.
The counting variant
Count subarrays summing to k. The brute force is a nested loop. The insight is that a subarray a[l..r] sums to k exactly when pre[r+1] − pre[l] = k, so for each right end you need the number of earlier prefixes equal to pre[r+1] − k. A hash map of prefix counts answers that in constant time.
count[0] = 1 before the loop. Without it you miss every subarray that starts at index 0, and the samples usually will not catch it.
Why this is not just Two Sum
It is Two Sum, and noticing that is the point. Two Sum asks for two values summing to a target; this asks for two prefixes differing by a target. Same hash-map-of-seen-values move, applied to derived quantities rather than the raw input. Once you see that, the pattern generalises: any time the answer depends on a difference of running quantities, a map of running values is available to you.
The variants worth recognising
- →Divisible by k — store running % k instead of running. Careful with negative remainders.
- →Equal numbers of two symbols — map one symbol to +1 and the other to −1, then count zero-sum subarrays.
- →Longest rather than count — store the first index each prefix value appeared at, not a count.
- →Two dimensions — build a 2D prefix table; a rectangle sum is four lookups by inclusion–exclusion.
The inverse: difference arrays
Prefix sums make range queries cheap on a fixed array. Difference arrays make range updates cheap when queries come at the end: add v at l, subtract v at r+1, and one prefix-sum pass at the end materialises the result. This is the standard answer to 'apply 10^5 range increments, then print the array', and it is the same identity read in the opposite direction.
Reading about a pattern is not the same as producing it under time pressure. The problems that drill this are in the curriculum, in order.