Prefix Sum
A prefix sum array pre-computes cumulative sums so any subarray sum [i, j] can be computed in O(1) as prefix[j+1] - prefix[i].
Prefix sum = a running odometer. To find the distance between mile markers 3 and 7, just subtract: odometer[7] - odometer[3]. No need to re-drive the road.
Build: prefix[0] = 0, prefix[i] = prefix[i-1] + arr[i-1]. Query: sum(i, j) = prefix[j+1] - prefix[i] (0-indexed). Common use: range sum queries, number of subarrays with sum = k (use hash map of prefix sums). Extend to 2D for matrix region sums: prefix[i][j] = grid[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1].
The 'subarray sum equals k' pattern uses a hash map from prefix sum to count. At each index, you want prefix[j] - prefix[i] = k, so you look up prefix[j] - k in the map. Initialize map with {0: 1} to handle subarrays starting at index 0. This generalizes to 'subarray sum divisible by k' using modular arithmetic — key insight: if two prefix sums have the same remainder mod k, the subarray between them is divisible by k. Prefix XOR works identically for XOR-based subarray queries.
Prefix sums transform range-query problems from O(n) per query to O(1) after O(n) preprocessing. For 'count subarrays with sum k', I maintain a running prefix sum and a hash map of how many times each prefix sum has appeared. At each index j, I need the count of i where prefix[j] - prefix[i] = k, so I look up prefix[j] - k. I always initialize the map with {0: 1} — that handles the case where a subarray starting from index 0 has sum k.
The prefix sum array is size n+1, not n. prefix[0] = 0 is the sentinel. Forgetting this causes off-by-one errors on the first element. In 2D prefix sums, the inclusion-exclusion formula must subtract the overlap exactly once: forget the subtraction and you double-count.