Prefix Sum
DSA · Arrays and Searching
Theory
A prefix sum array stores, at each position i, the total of all elements before it. After building it once in O(n), the sum of any range [l, r] is prefix[r+1] - prefix[l], answered in O(1). Prefix sums generalise to counts, 2-D grids and, combined with a hash map, to counting subarrays with a given sum.
Why we use it
It answers many range-sum queries quickly without re-adding the same numbers each time.
When to use it
Use it when you need many range totals, running totals, or subarray-sum questions.
How it works
- Start: prefix[0] = 0
- For i = 1..n: prefix[i] = prefix[i-1] + arr[i-1]
- Query sum(l..r)
- Answer = prefix[r+1] - prefix[l]
- Each query in O(1)
Syntax
prefix[0] = 0
prefix[i+1] = prefix[i] + arr[i]
sum(l..r) = prefix[r+1] - prefix[l]
Build: O(n) Each query: O(1)Example
sales = [5, 3, 8, 6, 2, 7]
prefix = [0]
for s in sales:
prefix.append(prefix[-1] + s)
print("Prefix:", prefix)
def range_sum(l, r):
return prefix[r + 1] - prefix[l]
print("Days 1 to 3 total:", range_sum(1, 3))
print("Days 0 to 5 total:", range_sum(0, 5))Key points
- Precompute once, query many times
- Range sum = prefix[r+1] - prefix[l]
- Works for counts and 2-D grids too
- Pairs with hash maps for subarray-sum problems