Why does a segment tree answer an arbitrary range query in O(log n) rather than O(range length)?
answer
- what does a fully-covered node cost?
- count the nodes that must recurse, per level
- the window has exactly two ragged ends
- only endpoints create partial overlap
- at most two partial nodes on each of log n levels
basics
~20 sA segment tree's nodes cover nested blocks of the index range. Any window is tiled by at most two stored nodes per level, so a query combines O(log n) precomputed aggregates instead of visiting every element.
solid answer
~50 sEach node of a segment tree stores the aggregate of a fixed block: the root covers the whole series, each node splits its block in half, and leaves are single positions. A query recurses from the root with three cases — a node disjoint from the requested window returns the identity, a node fully inside it returns its stored aggregate with no descent, and a node partially overlapping recurses into both halves. The key structural fact is that on any level at most two nodes can be partially overlapping, one straddling each endpoint of the window; everything between them is fully covered and stops immediately. So the recursion expands O(log n) nodes and combines at most about `2·log n` precomputed aggregates, independent of how wide the window is. Building costs O(n) bottom-up, and a point update repairs one root-to-leaf path in O(log n).
code
pseudocode · 9 linesquery(v, nodeLo, nodeHi, l, r):
if r < nodeLo or nodeHi < l:
return IDENTITY // disjoint: contributes nothing
if l <= nodeLo and nodeHi <= r:
return tree[v] // fully covered: stop here
mid = (nodeLo + nodeHi) / 2 // floor division
left = query(2*v, nodeLo, mid, l, r)
right = query(2*v + 1, mid + 1, nodeHi, l, r)
return combine(left, right)go deeper
Recall the three costs: build O(n), range query O(log n), point update O(log n), on a structure using a small multiple of n memory. Knowing a fully-covered node is returned without descending is the core idea to hold onto.
Explain the query's three cases and give the counting argument out loud: at most two nodes per level can straddle an endpoint, so only O(log n) nodes ever recurse. Be ready to name the identity for sum, minimum and maximum trees.
Show you know the practical edges — the roughly 4n slots of the array layout, the constant factor against a flat summary, and the edge-window bug that a wrong identity produces and that mid-series tests never catch.
Own the generality argument: any associative combine fits the same node contract, so the structure survives the next aggregate the product asks for. Weigh that flexibility against the code volume a team must maintain and test.
## The shape of the structure A segment tree over a series of length n is a binary tree over *index ranges*. The root owns `[0, n-1]`. A node owning `[lo, hi]` with `lo < hi` splits at `mid = (lo + hi) / 2` into a left child owning `[lo, mid]` and a right child owning `[mid+1, hi]`. Leaves own single positions. Every node stores one value: the aggregate — sum, minimum, maximum, or any associative combine — of the positions in its block. There are about `2n` such blocks, and the tree's height is ⌈log₂ n⌉. Because the blocks nest, a node's value is just `combine(left.value, right.value)`, which is what makes both the build and the update cheap. ## Why the query is logarithmic The query walks down from the root and classifies each node it meets against the requested window `[l, r]`: 1. **Disjoint** — the node's block shares nothing with the window. Return the identity (0 for sums, +∞ for minimum) and stop. 2. **Fully covered** — the node's block lies entirely inside the window. Return its stored aggregate and stop. **No descent happens here**, and this is where the saving lives: a node covering 100,000 positions contributes in one step. 3. **Partial** — the block straddles an endpoint of the window. Recurse into both children and combine. Now the counting argument. Fix a level of the tree. The blocks on that level are disjoint and ordered. A node is *partial* only if the window starts or ends strictly inside it, and only one block per level can contain `l` in its interior, and only one can contain `r`. Therefore **at most two nodes per level are partial**. Every other node on that level is either disjoint (pruned instantly) or fully covered (returned instantly). Since only partial nodes recurse, the recursion has at most 2 expanding nodes per level across ⌈log₂ n⌉ levels: **O(log n) nodes expanded, and at most about 2·log n canonical nodes actually combined**. The width of the window never enters the count. A useful mental picture: the window is paved with pre-measured tiles whose sizes are powers of two, big tiles in the middle and progressively smaller ones near the two ragged ends. You never measure anything; you add up a handful of measurements taken at build time. ## Build and update **Build is O(n), not O(n log n).** Each of the ~2n nodes is filled exactly once by combining its two children, which is constant work per node. Candidates often guess n log n by imagining n insertions into a tree of height log n; that would be the cost of inserting one at a time, not of a bottom-up fill. **A point update is O(log n).** Changing position `i` invalidates exactly the nodes whose block contains `i` — the single root-to-leaf path, one node per level. Rewrite the leaf, then recombine upward. Nothing else in the tree depends on `i`. ## What the constants look like The usual array layout puts the root at index 1 and the children of node `v` at `2v` and `2v+1`, which requires allocating about `4n` slots for an arbitrary n (the padded tree can be that large even though only ~2n nodes are meaningful). An iterative bottom-up variant over a size padded to a power of two needs only `2n`. So a segment tree is a few times the memory of the raw series, and each query does a handful of comparisons and combines per level — very fast in practice, but with a bigger constant and considerably more code than the alternative structure for the sum-only case. ## The honest caveats - **O(log n) is not O(1).** Against a flat precomputed summary of an immutable series, a segment tree query is strictly slower. Its value is entirely on the update side. - **The combine must be associative.** Grouping the canonical tiles left-to-right must give the same answer as any other grouping, because the query is free to combine them in the order the recursion returns them. Sum, min, max, gcd and bitwise ops all qualify; "the average" does not unless you store count alongside the total. - **The identity matters.** The disjoint case must return a value that cannot pollute the result: 0 for sums, +∞ for minimum, −∞ for maximum. Getting this wrong produces answers that are right on most inputs and wrong on windows that touch the edges — a classic subtle bug that unit tests on the middle of the series miss entirely. ## What to say in the interview Lead with the two-partial-nodes-per-level argument; it is the reason for the bound and it is what separates a memorised complexity from an understood one. Then name build O(n), point update O(log n), space a small multiple of n, and the requirement that the combine be associative with an identity.
- Building the tree over n values — is that O(n) or O(n log n), and why?O(n). The tree has about `2n` nodes and each is filled exactly once by combining its two already-filled children, so the work is constant per node. The n log n guess comes from imagining n separate insertions each descending a tree of height log n; a bottom-up fill never descends at all.
- What goes wrong if the disjoint case returns 0 for a range-minimum tree?Zero is not the identity for minimum, so any query whose recursion touches a disjoint node can return 0 instead of the true minimum — silently wrong whenever the real values are all positive. The disjoint case must return +∞ for minimum and −∞ for maximum; the identity is part of the structure's contract, not a detail.
- Which aggregates can a segment tree support, and which cannot it store directly?Any associative combine works: sum, minimum, maximum, gcd, bitwise and/or, matrix product. Aggregates that are not associative on the stored value alone — the mean, for instance — need a richer node: store total and count, combine both, and divide only at the end. If you cannot combine two adjacent blocks' summaries into the parent's summary, the value does not belong in a node.
Measuring a stretch of road when signposts already record the distance of every 1 km, 2 km, 4 km and 8 km block: you never re-measure the road, you add a few pre-measured blocks and only fuss over the ragged bit at each end.
saying these in an interview costs you the question
- Says the query descends to the leaves of the window
- Claims building the tree costs O(n log n)
- Thinks query cost grows with the width of the window
- Returns zero as the identity for a minimum tree
- Assumes any aggregate works without checking associativity