Range Queries and Segment Trees

Prerequisites: arrays, recursion and $O$-notation. Module 03 is used once, in the Recap.

Eight hours of sales

A shop records its sales hour by hour. Today's eight hours are

Two kinds of request arrive all day, interleaved. A manager asks for an aggregate over a range of hours: "total sales in hours 1 through 6" (27), or "the slowest hour in that stretch" (1). And the till sends a correction: "hour 3 was really 10, not 2". This is the dynamic range query problem: keep an array $a[0..n-1]$ under

• update(i, v): set $a[i]=v$;
• query(l, r): return $a[l]\oplus a[l+1]\oplus \dots \oplus a[r-1]$.

Ranges are half-open and 0-indexed in code, so "hours 1 through 6" is query(1, 7). Writing query(1, 6) returns 26 and silently drops hour 6, which is the commonest bug in this module.

Two obvious answers, each fast at one thing

Scan the range. An update is one write. A query reads $r-l$ elements, so $\Theta (n)$ in the worst case. A day of $n$ queries costs $\Theta (n^2)$.

Prefix sums. Store $P[k]=a[0]+\dots +a[k-1]$. Then any range sum is one subtraction, $P[r]-P[l]$, in $O(1)$. But a correction to $a[i]$ changes $P[i+1],\dots ,P[n]$: every later prefix. That is $\Theta (n)$ writes per update.

A = [6, 3, 9, 2, 7, 5, 1, 8]

def prefix_sums(a):
    P = [0]
    for x in a:
        P.append(P[-1] + x)
    return P

P = prefix_sums(A)
assert P == [0, 6, 9, 18, 20, 27, 32, 33, 41]
assert P[7] - P[1] == 27 == sum(A[1:7])
assert sum(A[1:6]) == 26          # off by one: hour 6 is missing
fixed = A[:3] + [10] + A[4:]
Q = prefix_sums(fixed)
assert [k for k in range(9) if P[k] != Q[k]] == [4, 5, 6, 7, 8]

Prefix sums have a second weakness: they need subtraction. There is no inverse for min, so the prefix minima $min(a[0.\mathrm{.6}])=1$ and $min(a[0.\mathrm{.0}])=6$ say nothing about the minimum over hours 1 to 6. (A sparse table, which stores the minimum of every block of length $2^j$, answers min in $O(1)$ by two overlapping blocks. It relies on $min(x,x)=x$, so it can't do sums, and it supports no updates at all.)

The waste is symmetric. Scanning recomputes, on every query, sums that nothing has changed. Prefix sums precompute, on every update, sums that nobody will ask for. We want something in between: each update should touch few stored sums, and each query should need few of them.

The model

We count node operations: reads and writes of stored aggregates, one word each. Combining two values with $\oplus$ costs $O(1)$. For string concatenation it really costs their length, so there the bound counts nodes, not characters.

The idea: every node knows its block

Pad $n$ up to a power of two $s$ (here $s=n=8$). Build a complete binary tree over the $s$ positions and store it in an array t the way a heap is stored: the root is t[1], the children of node $i$ are $2i$ and $2i+1$, and the leaves are t[s] .. t[2s - 1], leaf $s+j$ holding $a[j]$. Each node covers a block of consecutive positions: the leaves below it.

The code below fills every node straight from that definition. This is a stand-in, and it costs $O(n\log n)$; built bottom-up, from $t[s-1]$ down to $t[1]$, each node is one addition of its two children and the whole tree costs $s-1$ additions.

def block(node, size):
    """The half-open range of positions below a node."""
    lo, hi = node, node + 1
    while lo < size:
        lo, hi = 2 * lo, 2 * hi
    return lo - size, hi - size

def tree_from_definition(a, size, op=lambda x, y: x + y, identity=0):
    padded = list(a) + [identity] * (size - len(a))
    t = [identity] * (2 * size)
    for node in range(1, 2 * size):
        lo, hi = block(node, size)
        acc = identity
        for x in padded[lo:hi]:
            acc = op(acc, x)
        t[node] = acc
    return t

t = tree_from_definition(A, 8)
assert t[1:8] == [41, 20, 21, 9, 11, 12, 9]
assert all(t[i] == t[2 * i] + t[2 * i + 1] for i in range(1, 8))

Answering a query

A range $[l,r)$ is a union of blocks. The query takes the largest blocks that fit inside the range, and there are few of them. Think of it top-down. Start at the root. A node whose block lies inside $[l,r)$ is taken whole, and a node whose block misses the range is ignored. A node that straddles a boundary is split into its two children.

def query(t, size, l, r, op=lambda x, y: x + y, identity=0):
    """The aggregate of [l, r), top-down, and the nodes taken."""
    taken = []
    def visit(node, lo, hi):
        if hi <= l or r <= lo:     # the block misses the range
            return identity
        if l <= lo and hi <= r:    # inside the range: take it
            taken.append((node, t[node]))
            return t[node]
        mid = (lo + hi) // 2       # straddles a boundary: split
        left = visit(2 * node, lo, mid)
        return op(left, visit(2 * node + 1, mid, hi))
    return visit(1, 0, size), taken

assert query(t, 8, 1, 7) == (27, [(9, 3), (5, 11), (6, 12), (14, 1)])
assert query(t, 8, 0, 5) == (27, [(2, 20), (12, 7)])

The same nodes can be found bottom-up, with no recursion, which is how the array layout is usually used. Put two markers on the leaves $l+s$ and $r+s$ and move them up one level at a time. At each level, if the left marker sits on a right child, its parent's block starts to the left of the range, so the parent can't be taken. The marker's own node is taken, and the marker steps one node right. Symmetrically, if the right marker (which points one past the range) sits on a right child, the node just before it is taken. Then both markers move to their parents. The walk stops when the markers meet.

Why it is correct, and why it is fast

Correctness. The taken blocks are disjoint and together they are exactly $[l,r)$. Top-down, every position of the range lies under the root, and at each node it goes to exactly one child. It stops at the first node whose block lies wholly inside the range, which is taken. A position outside the range never gets inside a taken block, because only blocks inside the range are taken. By the invariant each taken node holds the aggregate of its block, so adding them in left-to-right order gives the aggregate of the range. The ordering matters, as the next section shows.

At most two taken nodes per level. Call a node split if it straddles a boundary of the range. A block contains the boundary $l$ in its interior only if it is the block at that level that holds position $l$, and the same for $r$. So each level has at most two split nodes. Every taken node's parent is a split node, since a parent inside the range would have been taken instead. And a split node that holds only one boundary has at most one child inside the range. One split node holding both boundaries has no child inside: its left child starts before $l$ and its right child ends after $r$. So at most two nodes are taken per level. There are ${\log }_{2}s$ levels below the root, and the root is taken only when the range is everything, so a query takes at most $2{\log }_{2}s$ nodes.

On eight leaves that is 6, and query(1, 7) took 4: one leaf from each end, then one node of two leaves from each end.

Updates. Changing $a[i]$ breaks the invariant only at nodes whose block holds $i$: the leaf and its ${\log }_{2}s$ ancestors. Rewrite the leaf, then recompute each ancestor from its two children, from the bottom up. That is exactly ${\log }_{2}s+1$ writes, and afterwards every node again holds its block's sum.

fixed = A[:3] + [10] + A[4:]         # hour 3 was 10, not 2
t2 = tree_from_definition(fixed, 8)  # stand-in: recompute all
changed = [i for i in range(1, 16) if t[i] != t2[i]]
assert changed == [1, 2, 5, 11]      # leaf 11 and its ancestors
assert [t2[i] for i in (11, 5, 2, 1)] == [10, 19, 28, 49]
assert query(t2, 8, 1, 7)[0] == 35

Complexity

Compare that with the two obvious answers. Scanning is $O(1)$ per update and $\Theta (n)$ per query. Prefix sums are $\Theta (n)$ per update and $O(1)$ per query. The tree is $O(\log n)$ for both. For ${10}^5$ updates and ${10}^5$ queries on ${10}^5$ positions, either obvious answer is about ${10}^{10}$ steps, while the tree is a few million.

Can we do better than $\log n$? Not by much. Pătraşcu and Demaine proved (2004) that for dynamic range sums in the cell-probe model, the model that charges only memory accesses, any data structure needs $\Omega (\log n)$ operations per update or query, amortized. This lesson states that bound without proof.

Any associative operation

Nothing in the proof used addition itself. It used two facts:

• Associativity, $(x\oplus y)\oplus z=x\oplus (y\oplus z)$, because the tree regroups the range into blocks;
• an identity $e$, with $e\oplus x=x=x\oplus e$, for padding and for empty ranges.

A set with such an operation is a monoid. Sum with 0, min with $+\infty$, max with $-\infty$, gcd with 0, string concatenation with "" and $2\times 2$ matrix product with the identity matrix are all monoids, and the same tree serves every one of them.

INF = float("inf")
mins = tree_from_definition(A, 8, min, INF)
assert mins[1:8] == [1, 2, 1, 3, 2, 5, 1]
assert query(mins, 8, 1, 7, min, INF)[0] == 1
cat = tree_from_definition(list("segment"), 8, lambda x, y: x + y, "")
assert query(cat, 8, 1, 6, lambda x, y: x + y, "")[0] == "egmen"
assert query(cat, 8, 0, 7, lambda x, y: x + y, "")[0] == "segment"

The identity matters for padding. Pad a min tree over $[5,3,9]$ with 0 and its root claims the minimum is 0. The padding must be the identity, $+\infty$ for min, or the invariant is false at every node above a padded leaf.

Order matters when $\oplus$ does not commute. Concatenation is associative but "ab" + "c" is not "c" + "ab". The top-down query above keeps the order on its own, because it always combines a left child's result with its right sibling's, in that order. The bottom-up walk takes nodes from both ends at once, so it needs two accumulators: nodes from the left marker are appended to the right end of left, nodes from the right marker are prepended to right, and the answer is left ⊕ right. A walk that appends both returns "tensegm" for all of "segment". Sums and minima hide that bug completely, so test it with a monoid that does not commute.

Speeding up an algorithm

Range queries also turn quadratic loops into $n\log n$ ones. A common shape is "for each element, aggregate over the earlier elements whose values fall in some range". Counting inversions is the standard example. For each $i$, how many $j<i$ have $a[j]>a[i]$? The obvious loop compares all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs.

Turn it around. Keep a sum tree indexed by value, where position $v$ counts how many elements of value $v$ have been seen so far. Walk the array. For each element, first query the positions above its value, which counts the earlier larger elements, then add 1 at its value. That is one query and one update per element: $O(n\log n)$. If the values are large, replace each by its rank among the distinct values first, so the tree has at most $n$ leaves.

def greater_before(a):
    """The definition, by brute force (a stand-in)."""
    return [sum(1 for j in range(i) if a[j] > a[i])
            for i in range(len(a))]

assert greater_before(A) == [0, 1, 0, 3, 1, 3, 6, 1]
assert sum(greater_before(A)) == 15
assert [sorted(A).index(x) for x in A] == [4, 2, 7, 1, 5, 3, 0, 6]
assert len(query([0] * 16, 8, 1, 8)[1]) == 3

On A the ranks are $4,2,7,1,5,3,0,6$. When the element 1 arrives (rank 0), six values have been seen, and the query over ranks $[1,8)$ reads their count, 6, from three nodes instead of comparing with six elements one by one. The totals are 15 inversions for $A$ and $\left(\genfrac{}{}{0ex}{}{65536}{2}\right)=2147450880$ pair checks for the brute force at $n=65,536$.

Updating a whole range

What if a correction adds $v$ to every hour in $[l,r)$? Doing it one position at a time costs $(r-l)\log n$. Lazy propagation keeps $O(\log n)$. The update takes the same at most $2{\log }_{2}s$ nodes a query would take. At each one it adjusts the stored sum (by $v$ times the block's length) then recomputes their ancestors on the way back, and leaves a pending tag: "add $v$ to everything below me". The tag is pushed down to the two children only when a later operation has to descend through that node. Every operation still touches $O(\log n)$ nodes. This lesson only sketches the idea and doesn't prove it.

A related trick uses the aggregates to search rather than to sum. With non-negative values, "the first position at which the running total reaches $k$" walks down from the root, going left whenever the left child's sum is still at least what remains of $k$. That is one root-to-leaf path, $O(\log n)$ reads.

Measure the claim

The proof says a query reads at most $2{\log }_{2}n$ nodes and an update writes exactly ${\log }_{2}n+1$. Below, the worst over 2,000 random queries (from random.Random(n)) is compared with the bound, and inversion counting is costed in node reads plus writes per $n{\log }_{2}n$, on a random permutation.

import math, random

measured = []
for n in (1024, 8192, 65536):
    r = random.Random(n)
    a = [r.randint(0, 99) for _ in range(n)]
    tree = [0] * (2 * n)
    tree[n:] = a
    for i in range(n - 1, 0, -1):
        tree[i] = tree[2 * i] + tree[2 * i + 1]
    worst = 0
    for _ in range(2000):
        l = r.randrange(n + 1)
        taken = query(tree, n, l, r.randrange(l, n + 1))[1]
        worst = max(worst, len(taken))
    r.randrange(n)
    perm = list(range(n))
    r.shuffle(perm)
    counts, ops = [0] * (2 * n), 0
    for x in perm:
        # reads: the nodes that count the earlier, larger values
        ops += len(query(counts, n, x + 1, n)[1])
        j = x + n
        while j:                   # writes: leaf to root
            counts[j] += 1
            ops += 1
            j //= 2
    lg = int(math.log2(n))
    measured.append((n, worst, 2 * lg, round(ops / (n * lg), 2)))

assert measured == [(1024, 15, 20, 1.6), (8192, 19, 26, 1.58),
                    (65536, 23, 32, 1.56)]

Random ranges rarely hit the worst case, which needs both boundaries to take a node at every level. The inversion column is flat, as $O(n\log n)$ predicts, and on these inputs it sits near 1.5. These are measurements on these inputs, not a theorem about the constant.

A problem that looks different

A game engine plays back a list of 50,000 moves. Each move is a rotation followed by a shift, so it is a small matrix. Designers keep editing single moves and keep asking where an object ends up if only moves $l$ through $r$ are applied. Nothing here is a sum, and the order of the moves certainly matters. Is there still a tree for it? The lab's last problem is a different one.

Practise

The lab has five parts. You build a tree and replay corrections on a new array, and the checks confirm that every node holds its block's sum in every frame. You trace the bottom-up walk node by node. You write one tree for any monoid, and a string check catches it if it ever combines out of order. You count the nodes your own inversion counter touches at three sizes. Finally you solve a problem that doesn't say what it is.

Recap

• You can now: say when prefix sums or a sparse table are enough and why neither survives updates; build a segment tree for any monoid; prove that a query takes at most two nodes per level and that an update rewrites exactly one path; and turn an "each element against the earlier ones" loop into $O(n\log n)$.
• Invariant: every node stores the aggregate of its block, $t[i]=t[2i]\oplus t[2i+1]$.
• Complexity achieved: $O(\log n)$ node operations per update and per query in the worst case, for any monoid, against $\Theta (n)$ for one of the two operations with scanning or with prefix sums; $O(n)$ build and space.
• Failure mode: combining the right-hand nodes in the wrong order for an operation that does not commute, padding with a value that is not the identity, or reading an inclusive range as half-open.
• In real software: the Linux kernel's interval trees (include/linux/interval_tree_generic.h) are red-black trees in which every node also stores the largest endpoint in its subtree (ITSUBTREE), kept up to date along the path on each change, and a search skips any subtree whose stored maximum rules it out. It is the same "node = aggregate of its subtree" invariant, on a balanced search tree instead of a fixed array.
• Retrieval: counting inversions needs values replaced by their ranks. For ${10}^5$ integers below ${10}^9$, how can the ranks be computed in $O(n)$ word operations? (Module 03 answers it.)

Check yourself

1. Why does a query take at most two nodes per level, and why do the taken blocks make up exactly the range? Use query(1, 7) on $A$ and explain why node 4 is not taken.
2. Replace sum by subtraction, which is not associative. What exactly breaks, and on which input can you show it?
3. A dashboard asks 1,000 range sums for every correction. Would you still use the tree, or prefix sums? At what ratio of queries to updates does the choice change?

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.