A prefix sum is a running total. You precompute an array where each position holds the sum of all elements up to that index. With that array in hand, the sum of any subarray becomes a single subtraction instead of a fresh loop. The same idea extends to counts, XORs, and products, and it pairs beautifully with hash maps for subarray-count problems.
When to use it#
Look for prefix sums when a problem asks about the sum, count, or aggregate of many different subarrays or ranges, especially when those queries repeat. If you find yourself recomputing overlapping sums in a nested loop, precomputing prefixes removes the redundancy. When the question asks “how many subarrays sum to K,” combine prefix sums with a hash map of previously seen sums.
Worked example#
Counting subarrays whose sum equals a target:
1def subarrays_with_sum(nums, k):
2 count = 0
3 running = 0
4 seen = {0: 1} # prefix sum -> how many times it occurred
5 for value in nums:
6 running += value
7 count += seen.get(running - k, 0)
8 seen[running] = seen.get(running, 0) + 1
9 return count
10
11print(subarrays_with_sum([1, 1, 1], 2)) # 2
For each position, running - k is the prefix sum we would need to have seen earlier for a valid subarray to end here.
Complexity#
Building a plain prefix sum array is O(n) time and O(n) space, after which each range query is O(1). The hash-map variant above is O(n) time and O(n) space in a single pass.
Practice problems#
- Range Sum Query Immutable
- Subarray Sum Equals K
- Contiguous Array (equal zeros and ones)
- Product of Array Except Self
- Find Pivot Index
- Range Sum Query 2D Immutable
For contiguous problems that need a growing window rather than a fixed sum, compare this with the sliding window technique, then head back to the pattern hub.