Segment Trees & Lazy Propagation
In short: a segment tree stores one aggregate per node, built bottom-up
from its two children, so a range query visits only nodes that are wholly
inside the range (total cover), wholly outside (disjoint), or split
between — about O(log n) nodes either way. It never subtracts, so it handles
min, max, gcd, anything combinable from two halves, unlike a Fenwick tree.
Lazy propagation extends it to range updates: a totally-covered node gets
its value and a pending tag updated without visiting its children, and the
tag is pushed down only right before something needs to read below it.
Quarry's latency panel doesn't want a total. It wants the fastest and slowest response between two minutes, while new measurements keep arriving. Every structure so far fails on that:
- the prefix row and the Fenwick tree both answer a range as prefix minus
prefix, and
mincan't be subtracted; - square-root blocks can do
min, but only at O(√n).
A segment tree handles any aggregate you can combine from two halves: sum, min, max, gcd, "longest run of healthy minutes", in O(log n) per query and per edit. It needs no subtraction, only a way to merge a left answer with a right answer. Later in the lesson it learns to take range updates too, using lazy propagation.
The shape
The root owns the whole log, minutes 0..n−1. Each node splits its range in
half and hands one half to each child, down to leaves that own one minute each.
Every node stores the aggregate of its range, computed from its two children.
There are about 2n nodes and the height is about log₂ n.
A query for l..r starts at the root. At every node it meets, exactly one of
three things is true:
- total cover: the node's range lies inside
l..r. Use its stored value and stop. - disjoint: no overlap at all. Contribute nothing and stop.
- partial: some overlap. Ask both children and combine their answers.
Here's the minimum over minutes 1..6, with the three outcomes in three colours. Badges show each node's stored minimum:
A range query visits a few nodes per level. Green nodes are wholly inside the range and answer for everything beneath them. Grey ones don't overlap, so they're skipped with everything beneath them. Only the partly covered ones go deeper.
The log is 5, 2, 7, 1, 3, 4, 6, 2. Every node's badge is the minimum of its range, built bottom-up from its children. Binary tree, 15 nodes, height 4.
Why only a few nodes per level? The range is contiguous, so on any level at most two nodes are partial: the ones containing its left edge and its right edge. Every other node there is wholly in or wholly out, and stops. So a query visits at most about four nodes per level, which is O(log n) in all.
Stored as a list
Like a heap, a complete tree fits in a flat list. Pad the log to a power of two,
size. Put the root at index 1, the children of node i at 2i and 2i + 1,
and the leaves at size .. 2·size − 1.
n = 6
size = 1
while size < n:
size *= 2
print(size, 2 * size)i = 5
print(2 * i, 2 * i + 1, i // 2)An edit sets the leaf and walks up the parents, recombining each one:
A query can be written either way, but the recursive version reads exactly like the three rules. Here it is with a bug that returns a wrong answer rather than crashing:
Minutes 4..7 hold 3, 4, 6, 2, so the minimum is 2. This prints 1, the minimum of the whole log: the root claims to be inside the range when only its right end is.
Now build and query your own. The drawing is your code's run: the tree is
Node objects, and the badges are whatever your code stores.
Your segment tree answering one range minimum. Change l and r, or the values, and count the nodes it visits.
❓ Cross-question — "Why not a Fenwick tree with min?" A Fenwick tree can keep prefix minima, but a range needs
prefix(r)minusprefix(l − 1). Forminthere's no minus. A segment tree never subtracts. It assembles the range from nodes that fit inside it exactly, so it needs only a combine step.
Range updates: lazy propagation
Quarry's backfill job is back: "add 2 ms to every request in minutes 0..5, the clock was off." A point update per minute is O(width · log n), which for a wide range is worse than rescanning.
The fix is the same idea as the block tags in lesson 2. When a range update totally covers a node, update that node's stored value and leave a pending tag on it ("everything below me is 2 higher") without visiting its children. That's O(log n) nodes, like a query.
The price is one rule: before you go below a node, push its pending tag down to its two children. Otherwise the children still hold the old values, and anything that reads them gets a stale answer. This sum tree shows the update, then a query that pushes, and what happens if it doesn't:
A range update stops at nodes it covers completely and leaves a tag there. The tag must move down one level before anything reads below it.
A sum tree over 5, 2, 7, 1, 3, 4, 6, 2. Leaves are left bare to keep the picture readable. Binary tree, 15 nodes, height 4.
In code, a node needs two fields, total and pending, and one helper:
4 * n cells is always enough for a recursive tree over any n.
How much does laziness save? An eager range update touches every leaf in the range, and a lazy one about four nodes per level, so about 4·log₂ w for a range of w minutes:
| range width w | eager (w leaves) | lazy (≈ 4·log₂ w) | lazy is cheaper by |
|---|---|---|---|
| 100 | 100 | 27 | 4× |
| 1,000 | 1,000 | 40 | 25× |
| 5,000 | 5,000 | 49 | 100× |
| 20,000 | 20,000 | 57 | 350× |
For narrow ranges both are cheap. At about 5,000 minutes, roughly three and a half days of Quarry's log, lazy is a hundred times less work: it's the wide ranges where laziness pays off.
Idioms & real-world patterns
Nodes that carry more than one number
Some aggregates need a few fields to combine. "Longest run of healthy minutes" can't be computed from the children's longest runs alone, because a run can cross the middle. Store, per node, the longest run touching its left edge, the longest touching its right edge, and the best anywhere. Combining is then a few lines, and point edits stay O(log n). That's the capstone exercise.
Quick practice
size = 8
i = 5
leaf = i + size
print(leaf, leaf // 2, leaf // 4)Minutes 4..7 hold 3, 4, 6, 2, so the minimum is 2. This prints 1, the minimum of the whole log, because the root's `l <= lo` is true on its own and the search never goes deeper.
🎯 Your turn
Build Quarry's range extremes: segment_log(values, ops). Each op is
["set", i, v] (minute i becomes v) or ["min", l, r] (smallest value in
minutes l..r, both included). Keep a segment tree of minima. Return the
answers to the min ops in order.
segment_log([5, 2, 7, 1, 3, 4, 6, 2], [["min", 1, 6], ["set", 3, 8], ["min", 0, 3], ["min", 3, 3]])→[1, 2, 8]
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green means this piece of Quarry is built. ✅