Segment Tree — Range Queries and Updates in O(log n)

What the structure actually is

Take an array of n elements and cover it with a binary hierarchy of intervals. The root covers [0, n). Any node covering [lo, hi) with more than one element splits at mid = (lo + hi) / 2 into children covering [lo, mid) and [mid, hi). Recursion stops at single-element intervals, which are the leaves. Each node stores one value: the aggregate of the elements its interval covers, computed by applying a merge function to its two children.

Nothing about this is specific to sums. The node value can be a minimum, a maximum, a greatest common divisor, a count of set bits, a pair of (best prefix, best suffix, best subarray) for maximum-subarray queries, or an entire small structure. The tree shape and all the traversal code stay identical; only the merge changes. That separation is why one segment tree implementation in a codebase usually serves five different query types with a function parameter.

The height is ceil(log2(n)) + 1, because each level halves the interval length. There are exactly n leaves and n - 1 internal nodes for a full decomposition, so the structure holds about 2n values in total -- a fact that matters more for the iterative layout below than for the recursive one. Every operation is a walk from the root toward the leaves and back, which is where the log n in every complexity bound comes from.

Canonical decomposition — why a query touches only O(log n) nodes

The claim that makes segment trees work is this: an arbitrary query range [l, r) can be written as the disjoint union of at most 2 log n node intervals. Those nodes are the canonical decomposition of the range, and since each one already holds its aggregate, answering the query is a matter of merging that handful of stored values.

The reason the count stays small is worth internalising, because it explains the recursion you write. Descend from the root. At each node, one of three things is true: the node's interval is entirely inside the query, in which case you take its value and stop; it is entirely outside, in which case you return the identity element and stop; or it straddles a boundary, in which case you recurse into both children. Straddling nodes are the only ones that branch, and at any level of the tree at most two nodes can straddle -- one containing l, one containing r. Every other node at that level is wholly in or wholly out. So the recursion is not a full traversal that happens to prune well; it is provably a pair of root-to-leaf paths with a fully covered block hanging off each.

Once you see the query that way the rest of the structure falls out. Point updates follow one path down and recombine on the way back up. Range updates need the lazy machinery precisely because they would otherwise have to descend into every covered node instead of stopping at the canonical ones.

Memory layout — the 4n array and the 2n alternative

The textbook recursive implementation stores the tree in a flat array with the implicit-heap indexing scheme: the root is at index 1, and the children of node i live at 2i and 2i + 1. No pointers, no allocation per node, excellent locality near the top of the tree.

The trap is sizing that array. Beginners allocate 2n because the tree has about 2n nodes, and then index out of bounds on inputs where n is not a power of two. The reason is that heap indexing does not compact the last level: when n is just above a power of two the tree is padded up to the next power of two internally, and the largest index actually written can approach 4n. Allocating 4 * n is the standard defensive answer and costs nothing you will notice. The tight alternative is 2 * 2^ceil(log2(n)), which is exact but easier to get wrong.

The iterative bottom-up layout avoids the question entirely. Place the n leaves at positions n .. 2n - 1 and let the parent of i be i / 2; the tree occupies exactly 2n slots with no padding. Queries walk inward from both endpoints, merging as they climb. This version is shorter, roughly twice as memory-efficient, and measurably faster because it has no call overhead -- but it is harder to extend with lazy propagation, which is why most production code that needs range updates keeps the recursive form.

Building in linear time

Building is O(n), not O(n log n), and the distinction is not a micro-optimisation when you rebuild often. Write the input elements into the leaf positions, then walk the internal nodes from the last one down to the root, setting each to the merge of its two children. Every node is visited exactly once and does constant work.

The tempting alternative -- insert the elements one at a time with n point updates -- costs O(n log n) for no benefit, because each insert re-walks a full root path that the bulk build handles implicitly. On a few million elements the difference is large enough to dominate the workload if you rebuild per batch, which is common when a segment tree backs a sliding analytical window.

The recursive build looks like this, with the merge left as a parameter:

def build(node, lo, hi):
    if hi - lo == 1:
        tree[node] = data[lo]
        return
    mid = (lo + hi) // 2
    build(2 * node,     lo,  mid)
    build(2 * node + 1, mid, hi)
    tree[node] = merge(tree[2 * node], tree[2 * node + 1])

Note the half-open intervals. Mixing half-open and closed conventions between build, query and update is the single most common source of segment-tree bugs, and it usually manifests as an answer that is correct except at range boundaries -- which test data drawn from the middle of the array will not catch. Pick one convention and enforce it in every signature.

Point update and range query in code

A point update changes one leaf and repairs the log n ancestors above it. The recursion mirrors the build: descend to the leaf, write it, then recombine on the way out.

def update(node, lo, hi, idx, value):
    if hi - lo == 1:
        tree[node] = value
        return
    mid = (lo + hi) // 2
    if idx < mid:
        update(2 * node, lo, mid, idx, value)
    else:
        update(2 * node + 1, mid, hi, idx, value)
    tree[node] = merge(tree[2 * node], tree[2 * node + 1])

The query is the three-case recursion described earlier, and the identity element in the disjoint case is what keeps it clean -- zero for sums, positive infinity for minimums, negative infinity for maximums, zero for a GCD.

def query(node, lo, hi, l, r):
    if r <= lo or hi <= l:
        return IDENTITY
    if l <= lo and hi <= r:
        return tree[node]
    mid = (lo + hi) // 2
    return merge(query(2 * node,     lo,  mid, l, r),
                 query(2 * node + 1, mid, hi, l, r))

Both functions are about ten lines and both are O(log n). If your merge is not constant-time -- merging sorted lists, for instance, as a merge-sort tree does -- multiply the bounds by the merge cost and re-check that the structure is still the right answer.

Lazy propagation — range updates without descending to every leaf

Adding a constant to every element of [l, r) naively means touching every leaf in the range, which is O(n) and defeats the structure. Lazy propagation fixes this by letting a node record an update it has applied to its own aggregate but has not yet pushed to its children.

The rule set is small. When a range update reaches a node whose interval is fully covered, apply the update to that node's stored aggregate and record a pending tag; do not recurse. When any later operation needs to descend through a node carrying a tag, push the tag into both children first -- applying it to their aggregates and merging it into their own tags -- then clear it. Because updates stop at exactly the canonical nodes a query would stop at, range updates become O(log n) too.

Two conditions have to hold, and violating either produces wrong answers rather than slow ones. First, the update must be applicable to an aggregate in constant time without seeing the underlying elements. Range-add with range-sum qualifies only if each node knows how many elements it covers, since the sum increases by delta * count -- store the interval length or derive it from hi - lo. Range-add with range-min is easier: the minimum just shifts by delta. Second, pending updates must compose. Two range-adds compose by addition. Range-assign composes by overwrite. Mixing add and assign in one tree requires a tag type that encodes both and a composition rule that respects order -- an assign wipes a pending add, but an add after an assign folds into it. Get that ordering backwards and the tree is silently wrong only on interleaved workloads.

Which merge functions are legal

The merge must be associative, and there must be an identity element -- in algebraic terms the values form a monoid. Associativity is required because the canonical decomposition merges pieces in whatever order the recursion produces them. Commutativity is not required, which is easy to miss and genuinely useful: matrix products, function composition and 'leftmost element satisfying a predicate' are all non-commutative merges that work fine, provided you merge the left child's result on the left.

Invertibility is a different property and it is what separates segment trees from Fenwick trees. Sum is invertible: knowing the prefix to r and the prefix to l, subtraction recovers the range. Minimum is not: knowing min[0, r) and min[0, l) tells you nothing reliable about min[l, r). A segment tree never needs inverses because it composes actual sub-ranges rather than differencing prefixes, which is precisely why it handles min, max, GCD, bitwise OR and 'is this range sorted' while a Fenwick tree does not.

Useful non-obvious merges: store (sum, prefix_max, suffix_max, best) per node to answer maximum-subarray on a range in O(log n); store a small frequency map to answer majority-element queries; store (min, count_of_min) to answer 'how many times does the minimum occur here'. Each is a drop-in change to the merge, with the rest of the structure untouched.

Fenwick trees, sqrt decomposition, and choosing between them

A Fenwick tree -- binary indexed tree -- answers prefix queries and point updates in O(log n) using exactly n words, about ten lines of code, and a loop over the low bits of the index. When the operation is invertible and you only need point updates, it beats a segment tree on every axis that matters: half the memory, better cache behaviour, and a constant factor that is typically two to four times faster in practice. Use it for prefix sums, inversion counting and order statistics over a value domain, and reach for the segment tree only when the operation stops being invertible or the updates stop being points.

Sqrt decomposition is the other neighbour. Split the array into blocks of about sqrt(n) and keep an aggregate per block; a query touches at most two partial blocks and sqrt(n) whole ones. That is asymptotically worse but genuinely competitive up to a few tens of thousands of elements, it takes fifteen lines, and it accommodates operations too awkward for a clean monoid. Mo's algorithm builds on the same decomposition to answer offline range queries that no online structure handles.

Two segment-tree variants are worth knowing by name. A sparse or dynamic segment tree allocates nodes on demand, so the index space can be the full range of 64-bit timestamps while memory stays proportional to the number of touched positions -- the standard alternative to coordinate compression when queries arrive online. A persistent segment tree keeps every historical version by copying only the O(log n) nodes an update touches, which makes 'the k-th smallest value in [l, r)' a difference between two versions and gives you point-in-time range queries for free.

A worked example — the sliding risk window

Concrete case: a trading system holds one million positions and must answer, on every tick, 'what is the total exposure of instruments l through r, and what is the single worst position in that band'. Positions are revalued constantly, so a few thousand point updates land per second alongside a few thousand queries.

Precomputed prefix sums are out -- a single revaluation invalidates every prefix from that index onward, so each update is O(n). Scanning is out for the same reason in reverse: a query over a wide band touches hundreds of thousands of entries. The segment tree makes both operations twenty node visits. Node values here are pairs, (sum, min), merged component-wise, which answers both questions in one traversal instead of maintaining two structures.

Now add the requirement that a haircut of five percent be applied to an entire sector at once. That is a range update, so the tree gains a lazy tag holding a multiplier. Sum scales by the multiplier; min scales by it too, but only if the multiplier is non-negative -- with a negative multiplier the minimum becomes the maximum, so the node must store both and swap them. This is the general shape of the constraint: the lazy tag has to be a legal action on the aggregate you store, and discovering that it is not usually means storing more per node rather than abandoning the structure.

Sizing: one million elements, four million nodes, sixteen bytes each for the pair plus a tag array is well under two hundred megabytes -- comfortably in-process, which is the regime segment trees are for.

Engineering notes that bite in production

Recursion overhead is real. The recursive form spends a meaningful fraction of its time on call frames. If a profile puts you inside query, converting to the iterative bottom-up form usually wins more than any algorithmic change, provided you do not need lazy tags.

Overflow is silent. Sum aggregates over 32-bit inputs overflow at the root long before they overflow at a leaf, and the wrong answer is a plausible-looking number. Store aggregates one width wider than the elements.

Identity elements must be honest. Using 0 as the identity for a minimum works until the data contains a negative number. Using the largest representable integer works until you add to it in a lazy push. Prefer an explicit optional or a sentinel checked at the merge.

Rebuild rather than clear. Zeroing a 4n array between queries in a batch loop costs more than the queries. Track a version stamp per node, or size the tree to the actual working set.

Know when not to use one. If the data lives in a database, a B-tree index with an aggregate rollup, a materialised view, or a column store's per-block min/max zone maps already implement this idea at a scale your process cannot hold in memory -- zone maps in particular are a flat, one-level segment tree over blocks, and they exist for exactly the reason described here. A segment tree is the right answer for an in-process, in-memory, high-mutation workload: an order book, a rate limiter's sliding window, a game's collision grid, a scheduler picking the least-loaded interval. It is the wrong answer for analytics you could have precomputed.