Prefix Sums

1. The signal

• “sum of the subarray from i to j”, asked many times
• “how many subarrays sum to k”
• “subarray with sum equal to / divisible by …”
• Any range aggregate where the array doesn’t change between queries
• A subarray-sum question where the values can be negative — this is the tell that a sliding window won’t work

2. The template

The array itself:

vector<long long> prefix(n + 1, 0);
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + a[i];
// sum of a[l..r] inclusive:
long long s = prefix[r + 1] - prefix[l];

const prefix = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + a[i];
const s = prefix[r + 1] - prefix[l];      // sum of a[l..r]

Using an n + 1 length array with prefix[0] = 0 removes every special case for l === 0. Do it this way and the off-by-one problems disappear.

With a hash map, for counting:

unordered_map<long long,int> seen{{0, 1}};   // the empty prefix
long long prefix = 0; int count = 0;
for (int x : a) {
    prefix += x;
    count += seen.count(prefix - k) ? seen[prefix - k] : 0;
    seen[prefix]++;
}

const seen = new Map([[0, 1]]);
let prefix = 0, count = 0;
for (const x of a) {
  prefix += x;
  count += seen.get(prefix - k) ?? 0;
  seen.set(prefix, (seen.get(prefix) ?? 0) + 1);
}

3. Why it works

The algebra is one line, and it’s worth writing out rather than memorising:

sum(l..r) = prefix[r] − prefix[l−1]

So asking “is there a subarray ending at r that sums to k?” rearranges to:

prefix[r] − prefix[l−1] = k     ⟺     prefix[l−1] = prefix[r] − k

That’s the whole insight. You stop searching forwards for a subarray and start looking backwards for a value — and looking backwards for a value is a hash map. It’s the same move as Two Sum, applied to running totals instead of elements.

4. Complexity

O(n) to build, O(1) per range query. The counting variant is a single O(n) pass with O(n) space.

5. Variants

• 2-D prefix sums — prefix[i][j] = sum of the rectangle from the origin. A submatrix sum is then four lookups with inclusion–exclusion. Week 11 territory.
• Prefix products — Product of Array Except Self is exactly this idea with multiplication and two sweeps.
• Prefix XOR — same structure, since XOR is its own inverse: xor(l..r) = pre[r] ^ pre[l-1].
• Difference array — the inverse. To add a value across many ranges, record +v at the start and −v just past the end, then prefix-sum once at the end. Turns O(n) per update into O(1).
• Prefix modulo — for “subarrays divisible by k”, key the map on prefix % k.

6. Traps

1. Forgetting the {0: 1} seed. Any subarray starting at index 0 goes uncounted. This is the bug in this pattern.
2. Storing the prefix before checking. Check for prefix − k first, then record the current prefix, or a zero-valued element counts itself.
3. Overflow in C++. Prefix sums grow fast; use long long.
4. Reaching for a sliding window on an array with negatives. It looks like it works on the examples and fails on the hidden tests.

7. Problems, easiest first

1. Product of Array Except Self — prefix and suffix sweeps
2. Subarray Sum Equals K — prefix + hash map, the core idea