Module 5
Prefix Sum
Precompute running totals once, and every range question becomes a subtraction. Add a hash map and you can count subarrays with any target sum.
A prefix sum array stores, for each position, the total of everything before it. With it, the sum of any range is one subtraction instead of a loop, which turns many O(n²) problems into O(n).
The module builds from plain range sums to the most important interview variant, prefix sums with a hash map (counting subarrays that sum to k, even with negative numbers), then difference arrays for range updates and 2D prefix sums for grids.
Best after: Hashing
Part 1
Learn the ideas
- 5.1Running Totals and Range SumsBuild `prefix[i]` = sum of the first i elements; then the sum of `a[l..r]` is `prefix[r + 1] − prefix[l]`.12 min
- 5.2Prefix Sums with a Hash MapA subarray sums to k exactly when two prefix sums differ by k, so count earlier prefix sums equal to `current − k` with a hash map.15 min
- 5.3Difference Arrays for Range UpdatesThe reverse of a prefix sum: mark +v at the start of a range and −v after its end, then one prefix sum applies every update.10 min
- 5.42D Prefix SumsExtend prefix sums to grids with inclusion-exclusion, so any rectangle's sum is four lookups.12 min
Part 2
Solve the problems
In order of difficulty. Each one shows the pattern it teaches.
Precompute once, answer many: O(n + q) instead of O(n · q).
Use the total to get the right-side sum for free: right = total − left − nums[i].
Prefix and suffix products: the answer at i is (product of everything left) × (product of everything right), without division.
Count subarrays with sum k, even with negative numbers, by counting earlier prefix sums equal to
sum − k.Turn "equal 0s and 1s" into "sum zero" by counting 0 as −1, then find the longest zero-sum subarray with first-seen indexes.
Apply many range additions in O(1) each with a difference array, then one prefix sum.
2D prefix sums: any rectangle's sum with four lookups using inclusion-exclusion.