Prefix Sums
Answer range questions instantly.
Suppose people keep asking, what's the total from day two to day five? Or day one to day seven? Adding up each range every time is slow. With one bit of preparation, every answer becomes O of one.

- What's the total from day 2 to day 5?
- Adding each time is slow
- Prepare once, answer instantly
Building prefix sums
A prefix sum list holds the running total up to each position, starting from zero. The total of any range is just two lookups, the running total at the end, minus the running total before the start. Run it. Days two to five total eighteen, with one subtraction.
from itertools import accumulate
sales = [4, 2, 7, 1, 8, 3, 10]
prefix = [0] + list(accumulate(sales))
print("prefix:", prefix)
def range_total(i, j):
return prefix[j + 1] - prefix[i]
print("days 2 to 5:", range_total(1, 4))prefix: [0, 4, 6, 13, 14, 22, 25, 35] days 2 to 5: 18
Prefix sums everywhere
Building the prefix list is O of N, once. After that, each range question is O of one. It's used for range totals, average over a period, and counting things in a range. And the same idea extends to two dimensions, for totals over areas in a grid.
| key | value |
|---|---|
| Build | O(n), once |
| Each query | O(1) |
| range(i, j) | prefix[j+1] - prefix[i] |
| 2D version | totals over a grid area |
Summary
Prefix sums trade a little preparation for instant range answers. Next, more practice with hashing. Anagrams.
Key takeaways- Running totals
- Two lookups per answer
- O(1) queries