test_reference_segtree

Segment tree built from $a = [2, 5, 1, 3, 7, 4]$. Each internal node stores the sum of its range. Tree nodes: $[0,5] \to [0,2],[3,5] \to [0,1],[2,2],[3,4],[5,5] \to [0,0],[1,1],[3,3],[4,4]$.

Query: compute $\text{sum}(1, 4)$. The query range $[1, 4]$ is highlighted in the source array.

Start at root $[0,5]$. The query $[1,4]$ partially overlaps, so we recurse into both children.

Left subtree $[0,2]$: recurse down. Node $[0,0]$ is outside query range – skip it.

Node $[1,1]$ fully inside $[1,4]$ – take value $5$. Node $[2,2]$ fully inside – take value $1$.

Right subtree $[3,5]$: node $[3,4]$ fully covered – take sum $= 10$. Node $[5,5]$ outside range – skip.

Result: $5 + 1 + 10 = 16$. Three nodes contributed – this is why queries are $O(\log n)$.

Now perform a point update: set $a[2] = 10$ (was 1). We walk from the leaf up to root.

Update leaf $[2,2]$: value changes from 1 to 10.

Update $[0,2]$: new sum $= [0,1]\text{.sum} + 10 = 7 + 10 = 17$.

Update root $[0,5]$: new sum $= 17 + 14 = 31$. Point update complete in $O(\log n)$.

Final tree reflects the updated array $a = [2, 5, 10, 3, 7, 4]$ with root sum $= 31$.

Sparse segment tree on range $[0, 7]$. Initially only the root $[0,7]$ exists. All other nodes are virtual.

Insert value 5 at position 2. Root $[0,7]$ partially covers – recurse left.

Allocate left child $[0,3]$ on-demand. This node did not exist before.

Recurse into $[0,3]$: position 2 is in the right half. Allocate $[2,3]$.

Allocate leaf $[2,2]$ for position 2.

Set leaf $[2,2] = 5$, bubble sums up: $[2,3]=5$, $[0,3]=5$, $[0,7]=5$.

Insert value 3 at position 6. Root recurses right this time.

Allocate right child $[4,7]$.

Position 6 is in $[6,7]$. Allocate $[6,7]$.

Allocate leaf $[6,6]$.

Leaf $[6,6]=3$. Bubble up: $[6,7]=3$, $[4,7]=3$, root $[0,7]=8$. Two paths allocated, rest of tree stays virtual.

Final state: only 8 nodes allocated out of a potential 15. Sparse trees use $O(q \log R)$ memory instead of $O(R)$.