Segment tree — build, range query, point update: Worked examples

This page is a drill through every situation a sum segment tree can throw at you. We reuse the machinery from the parent note: a Binary Tree over an array, Heap-style indexing (children of node $v$ are $2 v$ and $2 v + 1$ , root at index $1$ ), and the three query cases (no / total / partial overlap).

The scenario matrix

Cell	Scenario class	What breaks a beginner
A	Build on a power-of-2 array	clean tree, warm-up
B	Build on a non-power-of-2 array	uneven split, why $4 n$
C	Query = whole range $[0, n - 1]$	root total-overlap, stop instantly
D	Query = single index $[i, i]$	descends to one leaf
E	Query entirely inside the left half	right subtree never touched
F	Query straddling the mid boundary	the "at most 4 per level" fact in action
G	Point update, then re-query	repair the ancestor path only
H	Degenerate array $n = 1$	root is the leaf
I	Word problem (real data)	translating English → $(l, r)$
J	Exam twist: min-tree identity	$0$ is wrong, $+ \infty$ is right

The examples below hit every cell. The array we mostly use:

$a = [2, 1, 5, 3, 7, 4] (n = 6, not a power of 2)$

Example 1 — Cell A: build on a power-of-2 array

Worked example Build the sum tree for

$b = [4, 2, 6, 1]$ ( $n = 4$ ). Forecast: guess the root value before reading. (Hint: it is the total.)

Step 1 — split the top range. Node $1$ covers $[0, 3]$ . Since $l o \neq = hi$ , $mi d = ⌊(0 + 3) /2 ⌋ = 1$ , so children cover $[0, 1]$ and $[2, 3]$ . Why this step? The build recurrence only stops at leaves; anything wider must be split at $mi d$ .

Step 2 — recurse to leaves. $[0, 1] \to [0, 0], [1, 1]$ and $[2, 3] \to [2, 2], [3, 3]$ . Leaves store the raw values: $b [0] = 4, b [1] = 2, b [2] = 6, b [3] = 1$ . Why this step? A leaf's range is one element, so its "sum" is that element.

Step 3 — combine on the way up (post-order). $[0, 1] = 4 + 2 = 6, [2, 3] = 6 + 1 = 7, root [0, 3] = 6 + 7 = 13.$ Why this step? Sum is additive over the two disjoint child ranges, so parent $=$ left $+$ right — but only after both children are known.

Verify: $4 + 2 + 6 + 1 = 13$ ✓. Since $n = 4 = 2^{2}$ is a power of $2$ , the tree is a perfect binary tree with $2 n - 1 = 7$ nodes and no skipped indices.

Figure — Segment tree — build, range query, point update

Example 2 — Cell B: build on a non-power-of-2 array (why $4 n$ )

Worked example Build the sum tree for

$a = [2, 1, 5, 3, 7, 4]$ ( $n = 6$ ) and find the largest heap index used. Forecast: will any node land at an index $\geq 2 n = 12$ ?

Step 1 — the uneven split. Root $[0, 5]$ , $mi d = ⌊ 5/2 ⌋ = 2$ : left $[0, 2]$ , right $[3, 5]$ . Neither half is a power of $2$ , so the splits stay uneven all the way down. Why this step? $⌊(l o + hi) /2 ⌋$ never guarantees equal halves unless the length is a power of $2$ ; the left half here has $3$ elements, the right has $3$ .

Step 2 — recurse. $[0, 2] \to [0, 1] + [2, 2]$ ; $[0, 1] \to [0, 0] + [1, 1]$ . On the right, $[3, 5] \to [3, 4] + [5, 5]$ ; $[3, 4] \to [3, 3] + [4, 4]$ . Why this step? Same rule, applied to each odd-length range: one child gets the extra element.

Step 3 — combine. $[0, 1] = 3, [0, 2] = 3 + 5 = 8, [3, 4] = 10, [3, 5] = 10 + 4 = 14, root = 8 + 14 = 22.$ Why this step? Post-order combine again.

Step 4 — track the heap indices. Root $= 1$ . The deepest leaf sits on a long branch: $[3, 5]$ is node $3 \to [3, 4]$ is node $6 \to [3, 3]$ is node $12$ , and $[4, 4]$ is node $13$ . Why this step? Because the tree is unbalanced, index $13 > 2 n = 12$ — a plain $2 n$ array would be out of bounds. This is exactly why we allocate $== 4 n ==$ .

Verify: $2 + 1 + 5 + 3 + 7 + 4 = 22$ ✓, and $13 < 4 n = 24$ ✓ (safe).

Example 3 — Cell C: query the whole range

Example 4 — Cell D & E: single-index query inside the left half

Worked example On

$a = [2, 1, 5, 3, 7, 4]$ , compute query(1,1) (just $a [1]$ ). Forecast: the right subtree $[3, 5]$ — will it be touched at all?

Step 1 — root $[0, 5]$ vs $[1, 1]$ . Not no-overlap, not total (since $l = 1 > l o = 0$ ). Partial → recurse into $[0, 2]$ (node $2$ ) and $[3, 5]$ (node $3$ ). Why this step? The query point $1$ lies in the left half, but the recurrence still asks both children — the right one returns fast.

Step 2 — right child $[3, 5]$ vs $[1, 1]$ . Is $r < l o$ ? $1 < 3$ → yes, no overlap → return identity $0$ . Why this step? Cell E's whole lesson: the right subtree contributes nothing, so it dies in one test — never descending to its leaves.

Step 3 — left child $[0, 2]$ vs $[1, 1]$ . Partial → recurse $[0, 1]$ and $[2, 2]$ .

$[2, 2]$ vs $[1, 1]$ : $r < l o$ ( $1 < 2$ ) → no overlap → $0$ .
$[0, 1]$ vs $[1, 1]$ : partial → recurse $[0, 0]$ and $[1, 1]$ .
- $[0, 0]$ : $r < l o$ ? no. total? $1 \leq 0$ false → partial, but $l o = hi$ so children... actually $[0, 0]$ vs $[1, 1]$ : $hi < l$ means $0 < 1$ → no overlap → $0$ .
- $[1, 1]$ vs $[1, 1]$ : total overlap ( $1 \leq 1$ and $1 \leq 1$ ) → return tree for leaf $[1, 1]$ $= 1$ .

Step 4 — combine. $0 + (0 + (0 + 1)) = 1$ . Why this step? Every no-overlap branch injects the identity $0$ , so only the one matching leaf survives.

Verify: $a [1] = 1$ ✓. Right subtree touched once (one no-overlap test), never descended.

Example 5 — Cell F: straddling query (the "4 per level" fact)

Worked example On

$a = [2, 1, 5, 3, 7, 4]$ , compute query(1,4) (= $1 + 5 + 3 + 7$ ). Forecast: $1 + 5 + 3 + 7 = 16$ . Which precomputed nodes get reused whole?

Step 1 — root $[0, 5]$ vs $[1, 4]$ . Partial → recurse $[0, 2]$ and $[3, 5]$ . Why this step? The query boundary at $1$ and $4$ cuts through the root, so both halves matter.

Step 2 — left $[0, 2]$ vs $[1, 4]$ . Partial ( $l = 1 > 0$ ) → recurse $[0, 1]$ and $[2, 2]$ .

$[0, 1]$ vs $[1, 4]$ : partial → recurse $[0, 0]$ (no overlap, $0 < 1$ → $0$ ) and $[1, 1]$ (total → $1$ ). Sum $= 1$ .
$[2, 2]$ vs $[1, 4]$ : total overlap ( $1 \leq 2$ and $2 \leq 4$ ) → return $5$ . Whole node reused.
Left total $= 1 + 5 = 6$ .

Step 3 — right $[3, 5]$ vs $[1, 4]$ . Partial ( $r = 4 < 5$ ) → recurse $[3, 4]$ and $[5, 5]$ .

$[3, 4]$ vs $[1, 4]$ : total overlap ( $1 \leq 3$ and $4 \leq 4$ ) → return $10$ . Whole node reused.
$[5, 5]$ vs $[1, 4]$ : $hi < l$ ? no; $r < l o$ ? $4 < 5$ → no overlap → $0$ .
Right total $= 10 + 0 = 10$ .

Step 4 — combine. $6 + 10 = 16$ . Why this step? The wanted range decomposed into the precomputed nodes $[1, 1]$ , $[2, 2]$ , $[3, 4]$ — that is $\leq 4$ "canonical" pieces, the essence of $O (lo g n)$ .

Verify: $1 + 5 + 3 + 7 = 16$ ✓.

Example 6 — Cell G: point update then re-query

Worked example On

$a = [2, 1, 5, 3, 7, 4]$ , do update(4, 100) then re-run query(1,4). Forecast: the previous answer was $16$ ; index $4$ held $7$ . New answer?

Step 1 — descend to leaf for index $4$ . Root $[0, 5]$ : $mi d = 2$ , $4 > 2$ → go right to $[3, 5]$ (node $3$ ). Then $mi d = 4$ , $4 \leq 4$ → go left to $[3, 4]$ (node $6$ ). Then $mi d = 3$ , $4 > 3$ → go right to $[4, 4]$ (node $13$ ). Why this step? The update walks exactly one root-to-leaf path, chosen by comparing $i$ to $mi d$ at each node.

Step 2 — write the leaf. tree[13] = 100. Why this step? At a leaf the stored value is $a [i]$ , so we overwrite it.

Step 3 — repair ancestors on the way up. $[3, 4] = 3 + 100 = 103, [3, 5] = 103 + 4 = 107, root = 8 + 107 = 115.$ Why this step? Every ancestor summed the old $7$ ; only they need recomputing — all other nodes still hold correct values, giving $O (lo g n)$ .

Step 4 — re-query $[1, 4]$ . Same decomposition as Example 5: $[1, 1] = 1$ , $[2, 2] = 5$ , $[3, 4] = 103$ . Sum $= 1 + 5 + 103 = 109$ . Why this step? The canonical pieces are unchanged; only the value inside $[3, 4]$ moved.

Verify: new total $= 2 + 1 + 5 + 3 + 100 + 4 = 115$ ✓ (root). Query $= 1 + 5 + 3 + 100 = 109$ ✓ ( $= 16 - 7 + 100$ ).

Example 7 — Cell H: the degenerate single-element array

Example 8 — Cell I: word problem (real data)

Worked example A shop logs

daily sales over one week: sales = [12, 5, 0, 8, 20, 3, 9] (Mon…Sun). (1) What is total sales Tue–Fri? (2) A correction: Wednesday was actually $10$ , not $0$ . Re-answer Tue–Fri. Forecast: Tue–Fri = indices $1..4$ . Guess the two sums.

Step 1 — translate English to indices. Mon $= 0$ , Tue $= 1$ , …, Sun $= 6$ . "Tue–Fri" $= [1, 4]$ , "Wednesday" $=$ index $2$ . Why this step? A segment tree only speaks $(l, r)$ ; the hard part of word problems is this mapping.

Step 2 — query $(1, 4)$ . Sum of $5 + 0 + 8 + 20 = 33$ . Why this step? This is a standard partial-overlap query; we trust the machine (Example 5 shows the mechanics).

Step 3 — update $(2, 10)$ . Wednesday's leaf becomes $10$ ; ancestors repair. Why this step? Point update replaces the value and fixes the path — no full rebuild, unlike a Prefix Sum table which would need an $O (n)$ rescan.

Step 4 — re-query $(1, 4)$ . Now $5 + 10 + 8 + 20 = 43$ . Why this step? Only index $2$ changed, and it lies inside $[1, 4]$ , so the answer rose by $10 - 0 = 10$ .

Verify: $5 + 0 + 8 + 20 = 33$ ✓; $5 + 10 + 8 + 20 = 43 = 33 + 10$ ✓.

Example 9 — Cell J: the exam twist (min-tree identity)

Worked example Same array

$a = [2, 1, 5, 3, 7, 4]$ , but now a min segment tree. Compute query(3,5) (min of $3, 7, 4$ ). A student wrote the no-overlap return as 0. Show why that is wrong, then give the right answer. Forecast: the true minimum of ${3, 7, 4}$ is $3$ . What does the buggy code return?

Step 1 — what "combine" and "identity" become. For a min-tree, combine(x,y)=min(x,y). The identity is the value $e$ with $min (e, x) = x$ for all $x$ — that is $e = + \infty$ , not $0$ . Why this step? No-overlap nodes must contribute a value that cannot change the answer. For sum that is $0$ ; for min it must be larger than anything possible.

Step 2 — the bug. With identity $0$ , any no-overlap branch injects $0$ . Query $(3, 5)$ recurses; along the way some sibling returns $0$ , and $min (3, 0) = 0$ . Why this step? $0$ is smaller than every real element, so it wins the min and poisons the answer.

Step 3 — buggy result. The code returns $0$ (a value that is not even in the array). Wrong.

Step 4 — correct it. Return $+ \infty$ on no overlap. Then $min (3, + \infty) = 3$ , $min (7, + \infty) = 7$ , and the query correctly yields $min (3, 7, 4) = 3$ . Why this step? $min (x, + \infty) = x$ leaves real values untouched — exactly what an identity should do.

Verify: true answer $min (3, 7, 4) = 3$ ✓; buggy answer $0 \neq = 3$ ✗ (so the fix matters).

Recall

Recall Which query cell never touches the right subtree?

A query fully inside the left half ::: Cell E — the right child fails the overlap test in one comparison and returns identity.

Recall Why did

$n = 6$ need index $13$ ? Non-power-of-2 arrays split unevenly ::: The unbalanced branch pushes a leaf to heap index $13 > 2 n = 12$ , which is exactly why we allocate $4 n$ .

Recall After

update(4,100), which nodes changed on $a = [2, 1, 5, 3, 7, 4]$ ? Only the ancestors of index 4 ::: leaf $[4, 4]$ , then $[3, 4]$ , $[3, 5]$ , and the root — the single root-to-leaf path.

Recall What must a min-tree return on no overlap?

The min identity ::: $+ \infty$ , never $0$ .

Where to go next

Handle range updates efficiently → Lazy Propagation.
A lighter structure for prefix-style sums only → Fenwick Tree (BIT).
The recursion pattern behind build/query → Divide and Conquer.
Compare with the naive precompute → Prefix Sum.