A running total turns any range-sum question into one subtraction — pay O(n) up front, then answer every query in O(1). The same energy then hits the calendar: sort the intervals, merge the overlaps, and sweep the starts and ends to a peak.
Two patterns share this chapter because they share a soul: do the organizing work once, up front, so every question afterwards is nearly free. Prefix sums pre-add an array so any range sum becomes a single subtraction. Interval problems pre-sort a calendar so overlap becomes a purely local question — you only ever compare neighbors.
Both are also famous team players. Prefix sums plus Chapter 4's hash map produce Subarray Sum Equals K — the book's first genuine combo pattern, the kind of seam Chapter 23 teaches you to hunt. And the interval sweep is a warm-up for Chapter 19's greedy proofs and Chapter 14's heaps, which both love a sorted timeline.
Start with the honest baby version: Range Sum Query – Immutable Easy. You get a fixed array and then a stream of queries, each asking "what's the sum from index i to index j?" The naive move loops over the range every time — O(n) per query. With 10⁵ queries on a 10⁵-element array that's 10¹⁰ operations, and Chapter 3's budget meter buries you.
The fix is a bank statement. Keep a ledger P where P[t] is the running balance after the first t elements — with P[0] = 0 for the empty start. Then any range collapses to one subtraction:
sum(i..j) = P[j+1] − P[i]
Read it like money: the balance after day j, minus the balance before day i, is exactly what happened in between. Build the ledger in one O(n) pass, and every query after that costs two lookups and a minus sign.
Watch the ledger get built (one pass, each cell = previous cell + one element), then interrogate it: click any two array cells and the machine answers with exactly two shelf lookups. The stat cards keep score of what the naive re-scanner would have paid for the same questions — the gap is the whole pattern.
Note that the values include negatives and the ledger doesn't care — subtraction works on any running total. Hold that thought; it's about to matter a lot.
Now the interview classic: Subarray Sum Equals K Medium. Count how many contiguous subarrays sum to exactly k — negatives allowed. Brute force tries every (i, j) pair: O(n²) — every start times every end. The pattern does it in one pass, and the derivation is three lines of algebra:
Keep a map from prefix value → how many times it has occurred. At each element: update the running prefix, add seen[prefix − k] to the count, then record the current prefix. One pass, O(n) time and space. It's the Two Sum move played on the ledger instead of the array.
"Running total" is not really about addition — it's about any operation you can later undo. A few coats the same trick wears:
One honest boundary: the subtraction trick needs an inverse. Sums, products, XOR — fine. Range min or max queries have no undo (you can't "subtract" a minimum), so prefixes only give you "so far" scans there. Arbitrary range-min needs a segment tree or sparse table — genuinely rare in interviews, and saying that sentence out loud is itself worth signal points.
Second family, same soul. An interval is a [start, end] pair — a meeting, a booking, a range of taken seats — and interval problems arrive as an unsorted pile of them. Unsorted, "who overlaps whom?" is an all-pairs question: O(n²) — everyone against everyone. The organizing payment here isn't a ledger, it's a sort by start — O(n log n), sort once, then walk. After it, overlap becomes local: as you walk left to right, the only thing a new interval can possibly overlap is the block you're currently building. Everything earlier ended too soon; everything later starts too late.
That makes Merge Intervals Medium a five-line walk. Keep a current block [s, e]. For each next interval, one comparison: next.start ≤ e means overlap — fuse by extending e = max(e, next.end). Otherwise there's a gap: commit the block, start a new one. Its sibling Insert Interval Medium hands you the list already sorted and one newcomer: emit everything that ends before the newcomer starts, fuse everything that overlaps it into one block, emit the rest. Three phases, one pass, no sort needed — the input paid the organizing cost for you.
Meeting Rooms II Medium asks a different question: not "what does the merged calendar look like" but "how many rooms do I need?" — which is really "what's the maximum number of meetings alive at one instant?" Merging can't answer that; merging deliberately forgets how thick the pile was.
So change representation. Explode every meeting into two events: (start, +1) and (end, −1). Sort all events by time and sweep left to right with a running counter — +1 when a meeting begins, −1 when one ends. The counter traces occupancy over time, and its peak is the answer. O(n log n) — sort once, then walk; the same bill as merging, buying a different fact.
One subtlety earns real points: ties. If a meeting ends at 10:00 and another starts at 10:00, process the end first — the room frees up in time. Sort ends before starts at equal times, or you'll book a phantom room.
There's a popular twin solution: sort meetings by start and push end-times into a min-heap, reusing a room whenever the earliest end precedes the next start. Same answer, same complexity — and when the heap chapter (Chapter 14) hands you that tool, you'll recognize this problem waiting for it. For the interview, the sweep is easier to prove and harder to fumble.
One more family member, because it looks identical and sorts differently. Non-overlapping Intervals Medium: remove the fewest intervals so none overlap. Flip it — keep the most compatible intervals — and the winning move is to sort by end and greedily keep every interval that starts after the last kept one ended. Why end, not start? The earliest-ending interval leaves the most room for everyone after it; swapping it for any other kept choice never helps. That one-sentence swap argument is Chapter 19's exchange proof making an early cameo — greedy is legal here, and you just proved it.
And the endpoint fine print, which decides real test cases:
Zoom out and this chapter is one idea wearing two costumes. The naive versions of every problem here re-scan: re-add the range, re-compare all interval pairs — quadratic work that repeats itself. The pattern pays a one-time organizing cost — an O(n) ledger or an O(n log n) sort — after which a single linear walk (or an O(1) lookup) finishes the job. When you name the pattern in the room, name the payment too: "I'll build prefix sums in O(n), then each query is O(1)" is a complete, scored sentence.
The pattern, as a whiteboard skeleton:
The flagship is the combo: Subarray Sum Equals K Medium, prefix sums carrying the ledger and Chapter 4's hash map remembering it. The Python version is the imperative skeleton you'd write on a whiteboard; the Scala version makes the structure explicit — the running prefix is a fold, the seen-map is the fold's memory, and the whole solution is one foldLeft carrying a triple. Flip between them and notice it's the same five lines wearing two syntaxes.