Segment tree — build, range query, point update: Visual walkthrough

We use the array $a = [2, 1, 5, 3]$ throughout, because you can hold four numbers in your head while the shape of the argument does the heavy lifting.

Step 1 — The slow question we are trying to beat

WHAT. We have a row of boxes. Each box holds a number. Someone keeps asking: "add up the numbers from box $l$ to box $r$ ." Here $l$ (short for left) and $r$ (short for right) are just two box positions — the start and end of the stretch we care about.

WHY. Before inventing a clever structure, feel the pain of the obvious method. The obvious method is: walk every box from $l$ to $r$ and keep a running total. If the stretch is the whole array, that walk touches all $n$ boxes.

PICTURE. Below, the amber bracket marks a wanted stretch $[l, r] = [1, 2]$ . The naive method sweeps the cyan arrow across every box inside the bracket, one addition per box.

The cost of one such sweep is $r - l + 1$ additions — as many as there are boxes in the stretch. For a stretch covering the whole array that is $n$ additions. We want to answer without touching every box. That is the entire mission.

Step 2 — The one idea: precompute the sum of chunks

WHAT. Instead of adding boxes one at a time when the question arrives, we precompute (compute ahead of time) the total of certain chunks of consecutive boxes and store each total in its own little memory.

WHY. If a chunk's total is already sitting in memory, and a question happens to want exactly that chunk, we answer in one look — no walking. The trick is choosing chunks smartly so that any stretch someone asks for can be pieced together from a few stored chunks.

PICTURE. The whole array is one big chunk (top). We store its total, $2 + 1 + 5 + 3 = 11$ . Then we cut it into a left half and a right half and store each of those totals too. The amber labels are the stored sums.

The symbol $lo g_{2} n$ means: how many times do I halve $n$ to reach $1$ ? For $n = 4$ : $4 \to 2 \to 1$ , that is $2$ halvings, so $lo g_{2} 4 = 2$ .

Step 3 — Cutting all the way down: naming every chunk

WHAT. We keep cutting each chunk into two halves until a chunk is a single box. We name a chunk by the range of box indices it covers, written $[l o, hi]$ — $l o$ (low) is its first box, $hi$ (high) is its last box.

WHY. Naming the chunk by its own $[l o, hi]$ lets us describe the cut with a single, honest formula instead of hand-waving. The cut point is the middle index: $mi d = ⌊ \frac{l o + hi}{2} ⌋$

Term by term: $l o + hi$ adds the two ends, dividing by $2$ finds their midpoint, and $⌊ ⌋$ (the floor, meaning "round down to a whole number") snaps that midpoint to a real box index. The left half is then $[l o, mi d]$ and the right half is $[mi d + 1, hi]$ — note the $mi d + 1$ so the two halves do not share a box.

PICTURE. The full binary tree of chunks for $a = [2, 1, 5, 3]$ . Read it top-down: each parent chunk is sliced at its $mi d$ into the two children below it. The leaves (bottom row) are single boxes.

This tree of chunks is the segment tree. Every idea from here on is just "walk this tree cleverly."

Step 4 — Filling the tree (build): bottom-up sums

WHAT. Now we compute and store each chunk's total. We fill it bottom-up: a leaf's total is just its one box; a bigger chunk's total is its left child's total plus its right child's total.

WHY. A chunk's boxes are exactly the boxes of its left half plus the boxes of its right half, with no box shared and none missing (that was the point of the $mi d + 1$ ). Because sum is additive over disjoint pieces, the parent's total is honestly the sum of the two children's totals — we never need to re-add the original boxes.

tree [v] = {a [l o] tree [2 v] + tree [2 v + 1] if l o = hi (leaf: one box) otherwise (two halves)

Here $v$ is a node's address in a flat array called $tree []$ . We use the heap address trick: the root lives at address $1$ , and a node at address $v$ finds its children at $2 v$ (left) and $2 v + 1$ (right). So $tree [2 v]$ is "my left child's stored total" and $tree [2 v + 1]$ is "my right child's stored total."

PICTURE. The same tree, now with each node's stored total in amber. Watch the green arrows: two children flow up into their parent. Leaves fill first (they need no children), then $[0, 1] = 3$ , then $[2, 3] = 8$ , then the root $[0, 3] = 11$ .

The tree has $2 n - 1$ nodes (all the chunks), each filled exactly once, so build costs $O (n)$ .

Step 5 — Answering a query: the three-case walk

WHAT. To answer "sum over $[l, r]$ " we walk down from the root. At each node (chunk $[l o, hi]$ ) we compare that chunk to the wanted stretch $[l, r]$ and land in exactly one of three situations.

WHY. These three exhaust every possibility of how two ranges can sit relative to each other:

query = ⎩ ⎨ ⎧ 0 tree [v] left + right no overlap : r < l o or hi < l total overlap : l \leq l o and hi \leq r partial overlap (recurse)

No overlap ( $r < l o$ or $hi < l$ ): the chunk sits entirely outside the wanted stretch. It contributes nothing, so we return $0$ — the value that adds nothing, the identity of sum.
Total overlap ( $l \leq l o$ and $hi \leq r$ ): the chunk sits entirely inside the wanted stretch. Its whole precomputed total counts, so we return $tree [v]$ and stop — no need to look deeper. This early stop is the whole speedup.
Partial overlap: the wanted boundary slices through this chunk. We cannot use it wholesale, so we split — ask each child and add their answers.

PICTURE. Querying $[l, r] = [1, 2]$ . Each chunk is tinted by its case: grey = no overlap (skipped), amber = total overlap (its total is taken whole, and we stop), cyan-outline = partial (we recurse through it). The amber chunks we keep — $[1, 1]$ and $[2, 2]$ — are exactly the pieces that tile the wanted stretch.

Why $O (lo g n)$ ? On each of the $lo g n$ levels, at most $4$ chunks are ever the "partial" kind (two hugging the left boundary $l$ , two hugging the right boundary $r$ ); everything between them is one clean total-overlap grab. So work per query $\leq 4 lo g n = O (lo g n)$ .

Step 6 — Changing one box (point update): repair the path

WHAT. Suppose box $i$ changes to a new value. We must fix the stored totals — but only the ones that actually contain box $i$ .

WHY. Box $i$ lives in exactly one leaf, and that leaf lies inside exactly one chunk at each level — a single root-to-leaf path. Every chunk off that path still holds a correct total (box $i$ was never part of it). So we rewrite the leaf, then walk back up recomputing each parent as $tree [v] = tree [2 v] + tree [2 v + 1]$ .

PICTURE. Updating $a [2] = 10$ . The amber path root $\to [2, 3] \to [2, 2]$ is repaired; the greyed subtree $[0, 1]$ is untouched because it never contained box $2$ .

Step 7 — Edge and degenerate cases (never leave a gap)

WHAT / WHY / PICTURE — the corners the code must survive.

Single-box query $[i, i]$ . The walk descends straight to that leaf; every side chunk is no-overlap. Cost still $O (lo g n)$ .
Whole-array query $[0, n - 1]$ . The root is total overlap immediately — one grab, $O (1)$ here. The best case.
Empty / out-of-order stretch ( $l > r$ ). Every node is no-overlap, so the sum returned is $0$ — the correct answer for "no boxes."
$n$ not a power of two (like our $n = 4$ is, but $n = 5$ is not). The tree becomes lopsided — some leaves sit one level deeper. Heap addressing can then reach indices near $4 n$ , which is exactly why the $tree []$ array is sized $4 n$ .
A different combine, not sum. For a minimum tree the no-overlap case must return $+ \infty$ (the value that never wins a min), for maximum return $- \infty$ , for product return $1$ . Always return the identity of your combine — the value that changes nothing.

The one-picture summary

One tree does all three jobs. Build flows up (children into parents, $O (n)$ once). Query walks down choosing among no/total/partial overlap, grabbing whole chunks where it can ( $O (lo g n)$ ). Update walks down to one leaf then repairs back up along a single path ( $O (lo g n)$ ). The shared secret is halving: only $lo g n$ levels exist, so any traversal is short.

Recall Feynman retelling — say it back in plain words

Imagine a row of boxes with numbers. Adding a stretch of them by hand means touching every box — slow. So beforehand I glue the boxes into a pyramid: each brick is the total of the two bricks under it, all the way up to one brick holding the grand total. Building that pyramid touches each box once. Now when someone asks for a stretch, I stand at the top and walk down. If a brick sits fully inside the stretch, I grab its number and don't look deeper — that's the shortcut. If a brick sits fully outside, I ignore it. If the stretch cuts through a brick, I look at its two halves and add what they give me. Because the pyramid is only about $lo g n$ layers tall, I only ever inspect a handful of bricks per layer — fast. If one box changes, I don't rebuild the pyramid. Only the bricks stacked directly above that box are wrong, so I fix that one column from the box up to the top. Everything else was already right.

Recall Self-test

Why does a total-overlap node return immediately? ::: Its entire range is wanted, so its precomputed total is exactly what we need — recursing deeper can only re-derive the same number. Why exactly $lo g n$ levels? ::: Each level halves the chunk size; you can halve $n$ only about $lo g_{2} n$ times before reaching a single box. Which nodes change on an update to index $i$ ? ::: Only the root-to-leaf path through box $i$ ; every other chunk never contained $i$ . What must no-overlap return for a max-tree? ::: $- \infty$ , the identity of $max$ .

See also: Prefix Sum (the $O (1)$ -query, $O (n)$ -update rival), Fenwick Tree (BIT) (a lighter cousin for sums), Lazy Propagation (to make range updates fast too), Binary Tree and Divide and Conquer (the shapes this is built from).