🎓 A1Learner
🔍
0 of 47 lessons completed

Prefix Sums for Range Questions

A prefix sum is a running total of a list up to each position. It turns a range total into one subtraction.

Spot the signal

A problem asks for the total of many ranges in one list. The naive way adds the same items again and again.

nums = [3, 1, 4, 1, 5]
queries = [(0, 2), (1, 3), (2, 4)]
for left, right in queries:
    print(sum(nums[left:right + 1]))

The template

Build a prefix list with a leading 0. A range total is one subtraction.

nums = [3, 1, 4, 1, 5]
prefix = [0]
for value in nums:
    prefix.append(prefix[-1] + value)
print(prefix)
for left, right in [(0, 2), (1, 3), (2, 4)]:
    print(prefix[right + 1] - prefix[left])

Worked problem: count ranges

Count the ranges that add up to 5. A hash map holds how often each running total has appeared.

nums = [1, 2, 3, 4, 5]
target = 5
seen = {0: 1}
total = 0
count = 0
for value in nums:
    total += value
    count += seen.get(total - target, 0)
    seen[total] = seen.get(total, 0) + 1
print(count)

Example

changes = [5, -3, 2, -6, 4, 1]
prefix = [0]
for value in changes:
    prefix.append(prefix[-1] + value)
print(prefix[1:])
day = 1
while prefix[day] >= 0:
    day += 1
print(day)

Key points

  • Prefix sum: a list where each entry holds the total of all items up to that point.
  • Use a prefix sum to answer many range totals fast.
  • Build it in one pass by adding each item to the total so far.
  • Find a range total by subtracting the prefix before the range from the prefix at its end.
  • A prefix sum trades one building pass for instant range totals.

The code builds the running balance for each day. The balance first drops below zero on day 4. That day is the first day the balance goes negative.

Note

start the prefix list with 0 so a range starting at index 0 still works.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

The prefix list is [0, 2, 5, 9]. What is the sum of the elements at index 1 and index 2?