3.4.15 · D5Trees
Question bank — Segment tree — build, range query, point update
Every term used here (node range, overlap cases, identity element, heap indexing, repair-on-the-way-up) is built in the parent note — go re-read it if any word feels unearned.
True or false — justify
A leaf node and an internal node store the same kind of thing
True — both store the combined answer for their range; a leaf's range just happens to be one element, so its "combine" is trivially the element itself.
The two children of a node cover overlapping ranges
False — a node splits into and ; the
+1 guarantees the halves are disjoint, which is exactly why sums add cleanly.Every level of the tree holds the same total number of covered array elements
True — each level partitions the whole array into disjoint ranges, so summing range-lengths across one level always gives .
A segment tree over elements always has exactly nodes
False in effect — that count is for a perfect tree; when is not a power of two the heap-indexed layout leaves gaps, so we allocate rather than rely on .
You can build a min-segment-tree with the identical code as a sum tree, just swap + for min
Mostly true, but the identity must change too — the no-overlap return must become (min's identity), otherwise a
0 would wrongly win as the minimum.Doubling the array size doubles the query time
False — query is , so doubling adds only one extra level of work, not double.
A point update can leave the root value stale
False if you repair correctly — the update walks the root-to-leaf path and recomputes every parent on the way back up, so the root always reflects the new leaf.
The combine operation must be commutative for a segment tree to work
False, but it must be associative — we group children as
(left combine right) in a fixed order, so associativity is what we truly rely on; commutativity is optional (matters for non-commutative merges like string concatenation).Spot the error
if l <= lo and hi <= r: recurse both children — what's wrong?
Total overlap should return
tree[v] and stop, never recurse; recursing here throws away the whole speedup and visits every leaf, making query .Someone checks partial overlap first, then total, then no overlap. Why does this break?
The three cases aren't mutually exclusive in code order — a totally-overlapping node also "partially" matches loosely written conditions, so testing partial first makes you recurse when you should have stopped; the fixed order no → total → partial is mandatory.
return 0 is used for the no-overlap case in a product segment tree — bug?
Yes — 0 annihilates a product, forcing the whole answer to 0; the identity of multiplication is 1, so no-overlap must return 1.
After update, the code sets the leaf but forgets tree[v] = tree[2v]+tree[2v+1] on return. Symptom?
The leaf is correct but every ancestor still sums the old value, so range queries covering that index silently return wrong totals.
build(2*v, lo, hi) and build(2*v+1, lo, hi) — both children get the full range. What happens?
Infinite recursion (or a crash) — children must get the split ranges
[lo,mid] and [mid+1,hi]; giving both the full range never shrinks toward a leaf.tree = [0] * (2*n) for n = 5. Why might this crash?
With (not a power of 2) the heap indexing can reach indices past ; you need to be safe, or an index-out-of-range error strikes on some leaf.
mid = (lo + hi) // 2 then children [lo, mid] and [mid, hi]. What's the subtle bug?
Index
mid lands in both children — the ranges overlap, so that element is double-counted in every internal sum; it must be [lo,mid] and [mid+1,hi].In query, the recursion uses mid = (l + r) // 2 (query bounds, not node bounds). Wrong?
Yes —
mid must split the node's range [lo,hi], because that's how the tree was built; splitting the query range instead sends recursion to the wrong children.Why questions
Why does a total overlap stop, but a partial overlap recurse?
A totally-covered node's precomputed value is exactly a piece of the answer — no need to look inside; a partially-covered node mixes wanted and unwanted elements, so we must descend to separate them.
Why is query and not or ?
At each of the levels at most 4 nodes are ever expanded (two straddling each query endpoint); everything between them is a total-overlap that returns instantly.
Why do prefix sums beat segment trees for a read-only array?
With no updates, prefix sums give queries with a one-time build — strictly faster than the segment tree's ; the tree only pays off when updates are also needed (see Prefix Sum).
Why does the no-overlap case return an identity element specifically?
An identity leaves the running combine unchanged (e.g.
x + 0 = x), so a non-contributing node vanishes cleanly from the answer without corrupting it.Why can't we just use a plain Binary Tree with left/right pointers instead of the flat array?
You can, and it's conceptually identical — but heap indexing (
2v, 2v+1) avoids pointer storage and gives cache-friendly contiguous memory, mirroring the trick used in a Heap.Why does build compute children before the parent (post-order)?
A parent's value is
left + right; those child values must already exist, so we must finish both subtrees before combining — that's exactly a post-order traversal.Why does an update touch only nodes when the tree has of them?
Changing one array index affects only the ranges that contain that index, and exactly one node per level contains it — a single root-to-leaf path of length .
Why is a segment tree an instance of Divide and Conquer?
Each range problem is split into two independent half-range subproblems whose answers are combined — the defining split-solve-merge shape of divide and conquer.
Why does a range update (not point) need Lazy Propagation?
A range update could touch leaves naively; lazy propagation defers the work by tagging a node and pushing the change down only when a later query forces it, restoring .
Edge cases
What does build do when ?
The root is the single leaf
[0,0] storing a[0]; there's no split, and the tree has exactly one node.Query where l == r (a single index) — does the three-case logic still hold?
Yes — it walks down until one leaf totally overlaps
[l,l]; every other branch hits no-overlap and returns identity, so it correctly returns that one element.Query where l > r (empty range) — what should happen?
It should return the identity (0 for sum), since an empty range contributes nothing; guard against it at the top level, as the recursion assumes
l <= r.What if the query range exactly equals the whole array [0, n-1]?
The root is a total overlap on the very first call, so it returns
tree[1] immediately in — the best case.Update a[i] = val where val equals the current value — is the work skippable?
Logically nothing changes, but the code still walks and repairs the path (repairs are no-ops); you could early-exit, but correctness never depends on it.
For a min segment tree, what does querying an empty or non-overlapping range return, and why not 0?
— the identity of
min; returning 0 would falsely claim the minimum is 0 even when all elements are larger.What happens to unused tree[] slots (the gaps from over-allocation)?
They're never read by build/query/update because the recursion only visits indices along valid ranges; their leftover values (0 or garbage) are harmless.
Does the tree work if the array contains negative numbers?
Yes for sum/min/max — those combine functions handle negatives fine; only operations whose identity or algebra assumes non-negativity (rare) would care.
Compare with a Fenwick Tree (BIT) on this same task — when is the segment tree still preferred?
A BIT is smaller and faster for pure sum/point-update, but the segment tree generalizes to min, max, gcd, and range updates via lazy propagation — pick the tree when you need that flexibility.
Recall Self-check: the three query cases in order
No overlap → return identity ::: total overlap → return node value and STOP ::: partial overlap → recurse both children and combine.
Recall Self-check: which nodes change on a point update?
Only the ancestors on the single root-to-leaf path of the updated index — every other node keeps a correct value.