Lesson 09new · v2 format
Prefix Sums: Any Range Sum in O(1)
Spend one pass building running totals, then answer every 'sum from l to r' question with a single subtraction.
01Why it matters & the intuition
Range questions are everywhere: total sales between two dates, average temperature over a week, 'how many subarrays add up to k'. Re-adding a range each time costs O(n) per question, so 10⁵ questions on 10⁵ numbers is 10¹⁰ steps. A prefix-sum array turns each question into two lookups.
It's also the first time in the course you precompute something to make later work cheap — a trade that DP, hashing and caching all rely on.
Think of it like…
A car's odometer. To know how far you drove between two towns, you don't re-drive the road — you read the odometer at both towns and subtract. pre[k] is the odometer reading after the first k elements.
02The code blocks
Each block: the template in Python and C++, a line-by-line trace (press play and watch the highlighted line and the variables), the mistakes that cost the most debugging time, and a recall drill. Do the drill without scrolling up— that’s what makes it stick.
Block 1
Build a prefix-sum array
Use it for: Any time you'll ask 'sum of a[l..r]?' more than once, or need running totals.
1 · The template
pre = [0] * (len(a) + 1)
for i in range(len(a)):
pre[i + 1] = pre[i] + a[i]2 · Watch it run, line by line
▶pre = [0] * (len(a) + 1)2for i in range(len(a)):3pre[i + 1] = pre[i] + a[i]
Variables
—
3 · Classic mistakes
pre = [0] * len(a) # then pre[i + 1] = …One slot short: the last write, pre[len(a)], is out of range. The prefix array has n + 1 slots.pre[i] = pre[i - 1] + a[i] (starting at i = 0)pre[-1] is the last element in Python — silently wrong, not an error. The n + 1 version never needs i − 1.
4 · Recall it without looking
pre = [0] * ()
for i in range(len(a)):
pre[i + 1] = pre[] + a[i]Block 2
Range sum in O(1)
Use it for: Many range questions on data that doesn't change: subarray sums, averages over windows, 'sum between days l and r'.
1 · The template
def range_sum(pre, l, r):
# sum of a[l..r], both inclusive
return pre[r + 1] - pre[l]2 · Watch it run, line by line
▶def range_sum(pre, l, r):2# sum of a[l..r], both inclusive3return pre[r + 1] - pre[l]
Variables
- l
- 1
- r
- 3
3 · Classic mistakes
pre[r] - pre[l]Misses a[r]. With the n + 1 layout, 'up to and including r' is pre[r + 1].pre[r + 1] - pre[l - 1]Subtracts too little and breaks at l = 0. Everything before l is exactly pre[l].
4 · Recall it without looking
def range_sum(pre, l, r):
return pre[] - pre[]Block 3
Left total vs right total in one pass
Use it for: Balance/pivot index, 'split the array into two parts', product of everything except self (with × instead of +).
1 · The template
total = sum(a)
left = 0
for i in range(len(a)):
right = total - left - a[i]
if left == right:
break
left += a[i]2 · Watch it run, line by line
▶total = sum(a)2left = 03for i in range(len(a)):4right = total - left - a[i]5if left == right:6break7left += a[i]
Variables
- total
- 28
3 · Classic mistakes
right = sum(a[i + 1:]) inside the loopRe-summing the right side every step is O(n²). total − left − a[i] is O(1).left += a[i] before the comparisonThen left includes a[i] itself — the pivot must be on neither side.
4 · Recall it without looking
left = 0
for i in range(len(a)):
right = total - - a[i]
if left == right:
break
left a[i]03Key ideas
pre has n + 1 slots
pre[0] = 0 and pre[k] = a[0] + … + a[k − 1]. The extra leading zero removes every special case at l = 0.
Sum of a[l..r] = pre[r + 1] − pre[l]
Everything up to r, minus everything before l. Inclusive on both ends — memorise this one line.
Build once, query many
Building is O(n). Each query is O(1). Worth it as soon as there's more than a handful of queries.
Only for data that doesn't change
If values are updated between queries, the prefix array goes stale. That needs a Fenwick or segment tree (Module 19).
Same idea, other operations
Running product (careful with zeros), running XOR, running count of vowels — any operation you can 'undo' with a subtraction-like step.
04Cheat sheet
Every block from this lesson on one screen. Keep it open while you do the lab — then try the lab again without it.
# build: n + 1 slots, pre[0] = 0
pre = [0] * (len(a) + 1)
for i in range(len(a)):
pre[i + 1] = pre[i] + a[i]
# query: sum of a[l..r] inclusive
s = pre[r + 1] - pre[l]
# left vs right in one pass
total, left = sum(a), 0
for i in range(len(a)):
right = total - left - a[i]
...
left += a[i]
# shortcut: itertools.accumulate(a, initial=0) builds pre in one line05Complexity
| Approach | Build | Each range query |
|---|---|---|
| Re-add the range every time | — | O(n) |
| Prefix-sum array | O(n) | O(1) |
| Left/right balance scan | O(n) total | O(1) extra |
06Recognise it in a problem
These phrases in a problem statement should make you reach for a specific tool before you write any code.
| If the problem says… | …reach for |
|---|---|
| "sum of elements between index l and r", many queries, no updates | Prefix sums — O(1) per query |
| "balance / pivot / equilibrium index", "split into two equal halves" | Total − left, one pass |
| "subarray sum equals k" (values can be negative) | Prefix sums + a hash map of seen prefixes (Module 3) |
| "longest/shortest subarray with sum ≤ k", all values positive | Sliding window, not prefix sums |
| "range sum" but values change between queries | Fenwick / segment tree — prefix array goes stale |
07Decode drills
You won’t solve these here. Read each problem the way an experienced engineer would: circle the clues in your head, pick the technique family and the complexity you must hit. Then check the clues you missed.
Monthly sales report
A shop records daily sales for a year. Managers ask many questions like "what were total sales from day l to day r?". Sales figures never change once recorded.
Constraints: n = 365 · q ≤ 10⁵ questions
08Check your understanding
09Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Answer range-sum queries
Given a and a list of queries where each query is [l, r] (inclusive), return a list with the sum of a[l..r] for each query. Build a prefix array once — don't re-add each range.