DSA · Chapter 8 of 40
Prefix Sum
A prefix sum array stores the running total of a list, so the sum of any range can be found in O(1) by subtracting two prefix values. Building it costs one O(n) pass.
This is the standard trick when a problem asks many range-sum queries, or counts subarrays with a given sum.
Range sums
With prefix[i] = sum of the first i elements, sum(l..r) = prefix[r+1] - prefix[l].
Counting subarrays
Combine prefix sums with a hash map of seen sums to count subarrays that add up to a target in O(n).
Example 1 (python)
nums = [2, 4, 1, 3]
prefix = [0]
for n in nums:
prefix.append(prefix[-1] + n)
# sum of index 1..2
print(prefix[3] - prefix[1])Output
5Any range sum becomes one subtraction.
Example 2 (python)
def count_subarrays(nums, k):
counts = {0: 1}
total = result = 0
for n in nums:
total += n
result += counts.get(total - k, 0)
counts[total] = counts.get(total, 0) + 1
return result
print(count_subarrays([1, 1, 1], 2))Output
2Prefix sums plus a hash map count subarrays in O(n).
Key points
- Prefix sums answer range queries in O(1) after O(n) setup.
- sum(l..r) = prefix[r+1] - prefix[l].
- Pair with a hash map to count subarrays with a target sum.
- The same idea extends to 2D grids.
💡 Note: Use prefix sums when the array does not change between queries; otherwise consider a Fenwick tree.