Prefix Sum
The Intuition
Picture a cash register receipt. Every line has a running total on the right side. You bought 10 items and you want to know how much items 5 through 8 cost. You don't pull out a calculator and re-add those four items. You look at the running total after item 8, then look at the running total after item 4, and subtract. One operation. Done.
That's prefix sum. You walk through your array once, building a running total at each position. Now any range query is just a subtraction. Want the sum from index 3 to index 7? Take prefix[8] minus prefix[3]. You never touch the elements in between. It doesn't matter if the range has 5 elements or 5 million. One subtraction either way.
The reason you build the prefix array with one extra slot at the front (initialized to zero) is so the math stays clean. If you want the sum starting from index 0, you need a "before index 0" value to subtract from. That zero handles it. No special cases.
Here's where it gets really interesting. When a problem asks "how many subarrays sum to k?", you combine prefix sums with a hash map. At each position, your running total is some number. If you've seen (running total minus k) before, that means there's a subarray ending right here that sums to exactly k. You're converting a two-pointer search problem into a hash map lookup. O(n) total, no nested loops.
Range sum queries, subarray sum equals K, finding equilibrium indices, or any problem that benefits from precomputed cumulative values.
- Needs updates (use Segment Tree)
- Non-contiguous ranges (use two pointers or DP)
Variations:
- 1D Prefix Sum: Standard array prefix sums for range queries.
- 2D Prefix Sum: Matrix region sum queries using inclusion-exclusion.
- Prefix Sum + Hash Map: Count subarrays with a given sum using running totals.
- empty array
- single element
- all zeros
- negative numbers
Key Points
- •Build prefix array where prefix[i] = sum of arr[0..i-1]
- •Range sum query: sum(l, r) = prefix[r+1] - prefix[l]
- •Use hash map for subarray sum equals k problems
- •Works with XOR, product, and other associative operations
Code Template
1 def build_prefix_sum(arr):
2 """Build prefix sum array for O(1) range queries."""
3 prefix = [0] * (len(arr) + 1)
4 for i in range(len(arr)):
5 prefix[i + 1] = prefix[i] + arr[i]
6 return prefix
7
8 def range_sum(prefix, left, right):
9 """Sum of arr[left..right] inclusive."""
10 return prefix[right + 1] - prefix[left]
11
12 def subarray_sum_k(arr, k):
13 """Count subarrays that sum to k."""
14 count = 0
15 current_sum = 0
16 prefix_counts = {0: 1}
17
18 for num in arr:
19 current_sum += num
20 count += prefix_counts.get(current_sum - k, 0)
21 prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
22
23 return countCommon Mistakes
- Off-by-one error in prefix array indexing
- Forgetting to initialize hash map with {0: 1} for subarray sum
- Not considering negative numbers in subarray sum problems