Prefix Sums: Range Totals in One Subtraction
A fitness app stores your daily step counts for a whole year, and its charts keep asking "how many steps from day 40 to day 95?" Adding up 56 numbers for every question is fine once, but the app asks thousands of times. A little preparation turns every one of those questions into a single subtraction.
The rule
Store running totals once; any range is one subtraction.
A prefix sum list holds, at position i, the total of everything before position i. It starts with 0, for "nothing added yet":
def build_prefix(nums):
prefix = [0]
for x in nums:
prefix.append(prefix[-1] + x)
return prefix
def range_sum(prefix, left, right): # inclusive of both ends
return prefix[right + 1] - prefix[left]
steps = [4, 2, 7, 1, 5, 3]
prefix = build_prefix(steps) # [0, 4, 6, 13, 14, 19, 22]
range_sum(prefix, 1, 3) # 14 - 4 = 10, which is 2 + 7 + 1The total up to the end of the range, minus the total before its start, leaves exactly the range. Building costs one pass; every question afterwards costs one subtraction. The leading 0 is what lets a range that starts at day 0 work too. For a year of 365 days and 10,000 questions, that is 365 additions once, instead of up to 3.65 million.
Now combine it with the complement lookup from this section. How many stretches of consecutive days add up to exactly k? A stretch ending here sums to k exactly when some earlier running total equals the current total minus k. So keep a dictionary counting the running totals seen so far, and look up total - k at every step:
def count_stretches(nums, k):
seen = {0: 1} # the empty start: total 0, seen once
total = found = 0
for x in nums:
total += x
found += seen.get(total - k, 0)
seen[total] = seen.get(total, 0) + 1
return foundThe shortcut
A range total is "up to the end" minus "before the start". For counting stretches, flip it into a lookup: at each running total, ask "how many times have I already seen total - k?" It is the pair-finding book again, holding running totals instead of prices.
Day 0, value 3
Running total 3. Need 3 − 7 = −4: never seen. Book: {0: 1, 3: 1}.
Why not a sliding window here? A window relies on "adding an item raises the total, dropping one lowers it". With negative numbers like −2 that promise breaks, and prefix sums are the safe tool.
Drills
Answer fast — trust the rule.
With prefix = [0, 4, 6, 13, 14, 19, 22], what is range_sum(prefix, 2, 5)?
Why does the prefix list start with 0?
What does count_stretches([1, 2, 3], 3) return?
What breaks if seen starts as an empty dictionary instead of {0: 1}?
Why can a sliding window not count stretches adding up to k when values may be negative?
Remember
- Store running totals once; any range is one subtraction.
- Shortcut: "up to the end" minus "before the start"; for counts, look up
total - k. - Trap: forgetting the starting 0, or using a sliding window on negative numbers.