Lesson 10new · v2 format
Difference Arrays & Sweep Lines: Many Range Updates, One Pass
Record where each change starts and stops, then let one running sum apply them all.
01Why it matters & the intuition
Prefix sums answer many range questions. Difference arrays handle the reverse: many range updates — 'add 5 to every seat from 10 to 40', 'this flight carries 30 passengers from stop 2 to stop 7'. The same +1/−1 idea becomes the sweep line: sort the start and end events and you know how many things overlap at any moment. That covers meeting rooms, peak server load and car-pooling problems.
Think of it like…
A bus route. You don't track every passenger at every stop — you note '+3 got on at stop 2' and '−3 got off at stop 7'. Walking the route and keeping a running count tells you exactly how full the bus is between any two stops.
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
Mark a range update in O(1)
Use it for: Many 'add v to every index l..r' operations before you need the final values.
1 · The template
diff = [0] * (n + 1)
for l, r, v in updates:
diff[l] += v
diff[r + 1] -= v2 · Watch it run, line by line
▶diff = [0] * (n + 1)2for l, r, v in updates:3diff[l] += v4diff[r + 1] -= v
Variables
- n
- 5
3 · Classic mistakes
for i in range(l, r + 1): a[i] += vCorrect, but O(length) per update — 10⁵ updates on 10⁵ cells is 10¹⁰ steps.diff = [0] * nAn update ending at n − 1 writes diff[n], which doesn't exist. Keep one spare slot.
4 · Recall it without looking
for l, r, v in updates:
diff[] += v
diff[] -= vBlock 2
Rebuild values with a running sum
Use it for: Right after marking all updates — one pass turns markers into real values.
1 · The template
a = [0] * n
running = 0
for i in range(n):
running += diff[i]
a[i] = running2 · Watch it run, line by line
▶a = [0] * n2running = 03for i in range(n):4running += diff[i]5a[i] = running
Variables
—
3 · Classic mistakes
a[i] = diff[i]diff only stores changes. The value at i is the sum of every change up to i.running = 0 inside the loopResets the total every step — you'd just copy diff.
4 · Recall it without looking
running = 0
for i in range(n):
running diff[i]
a[i] = Block 3
Sweep line: +1 on start, −1 on end
Use it for: Meeting rooms, peak concurrent users, maximum overlap, 'is anyone double-booked?'.
1 · The template
events = []
for start, end in intervals:
events.append((start, +1))
events.append((end, -1))
events.sort()
now = best = 0
for time, delta in events:
now += delta
best = max(best, now)2 · Watch it run, line by line
▶events = []2for start, end in intervals:3events.append((start, +1))4events.append((end, -1))5events.sort()6now = best = 07for time, delta in events:8now += delta9best = max(best, now)
Variables
—
3 · Classic mistakes
Sorting ties with +1 before −1A meeting ending at 4 and one starting at 4 would be counted as overlapping. Decide the tie rule on purpose.Checking every pair of intervalsO(n²). Sorting 2n events is O(n log n).
4 · Recall it without looking
for start, end in intervals:
events.append((start, ))
events.append((end, -1))
events.sort()
for time, delta in events:
now += delta
best = (best, now)03Key ideas
Change at l, undo at r + 1
diff[l] += v; diff[r + 1] -= v. Every update is two writes, however long the range.
The prefix sum of diff is the answer
A running total over diff turns the start/stop markers back into real values — difference arrays and prefix sums undo each other.
Sweep line = difference array on sorted times
When positions are timestamps (possibly huge), don't allocate an array — make (time, ±1) events, sort, and keep a running count.
Decide the tie rule
At the same time, process −1 before +1 if a meeting ending at 4 frees the room for one starting at 4 (half-open intervals). Otherwise use the opposite order.
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.
# many range updates → mark, then one running sum
diff = [0] * (n + 1)
for l, r, v in updates: # inclusive l..r
diff[l] += v
diff[r + 1] -= v
running, a = 0, [0] * n
for i in range(n):
running += diff[i]
a[i] = running
# sweep line: peak overlap of [start, end) intervals
events = sorted([(s, 1) for s, e in intervals] + [(e, -1) for s, e in intervals])
now = best = 0
for time, delta in events:
now += delta
best = max(best, now)05Complexity
| Approach | Time | Extra space |
|---|---|---|
| Loop over each range (naive) | O(q · n) | O(1) |
| Difference array + one running sum | O(q + n) | O(n) |
| Sweep line over sorted events | O(q log q) | O(q) |
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 |
|---|---|
| "add v to all elements from l to r", many updates, answer at the end | Difference array |
| "maximum number of overlapping intervals", "meeting rooms needed" | Sweep line (+1 start, −1 end) |
| "passengers / bookings between stops", capacity check | Difference array over stops (car pooling) |
| "sum of range l..r" questions on fixed data | Prefix sums (the inverse tool) |
| Updates and questions mixed together, answered immediately | Fenwick / segment tree |
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.
Stadium seat upgrades
A stadium has n seats in a row, all priced at 0. Each promotion adds v rupees to every seat from l to r. After all promotions, print the final price of every seat.
Constraints: n ≤ 10⁵ · promotions ≤ 10⁵
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”.
Apply range additions
Start with an array of n zeros. Each update is [l, r, v]: add v to every index from l to r inclusive. Return the final array. Use a difference array — each update should cost O(1).