Prefix Sums & Difference Arrays
Intermediate · 18 min read · Problem-Solving Patterns, Arrays & Strings
Answer range-sum questions in O(1) and count subarrays with a hash map.
"What's the sum of elements from index 3 to 9?" A loop answers it in O(n). Ask that a thousand times and you've done a thousand loops — over the same numbers. A prefix sum array does the adding once, up front, and then answers every range-sum question with a single subtraction.
The idea
Let p[i] be the sum of the first i elements. Then any range sum is a difference of two prefixes:
Prefix sums + hash map: counting subarrays
The same identity, read backwards, is the key to a whole family of problems. A subarray ending at i sums to k exactly when some earlier prefix equals prefix(i) − k. So walk once, keep a count of every prefix seen so far, and at each step ask "how many earlier prefixes equal current − k?"
Worked problems
Two prefixes with the same remainder mod k bracket a subarray whose sum is a multiple of k. Count remainders:
The reverse: difference arrays for range updates
Prefix sums make range queries cheap. Difference arrays make range updates cheap. To add v to every element in [l, r], mark only the two edges, then take one running sum at the end:
Practice ladder
Interview questions
- Why initialise the hash map with prefix 0 when counting subarrays that sum to k?
- When do you store counts and when do you store the first index?
Further reading
Key takeaways
- A prefix array (length n + 1, p[0] = 0) answers any range sum in O(1): p[r + 1] − p[l].
- Prefix + hash map counts subarrays with a target sum in O(n), negatives included: look up prefix − k, then store.
- Seed the map (0 → 1 for counts, 0 → −1 for longest); counts for "how many", earliest index for "longest".
- Transform problems into zero-sum form; use Math.floorMod for remainders.
- Difference arrays make range updates O(1), with one prefix pass at the end.