AI Hints
Home›DSA in Python Tutorial›Windows and Prefixes
DSA in Python · Lesson 27 of 132

Prefix Sums

Answer range questions instantly.

⏱ 2 min read▶ Video at 31:00🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Prefix Sums
From the video: Prefix Sums
  • 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.

prefix.pypython
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))
Output
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.

keyvalue
BuildO(n), once
Each queryO(1)
range(i, j)prefix[j+1] - prefix[i]
2D versiontotals 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
Next up: Practice: Valid Anagram — same letters, different order