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

The root [0,5] splits at $mid=\lfloor (0+5)/2\rfloor =2$ into [0,2] (heap index 2) and [3,5] (heap index 3). (a) Node 3 covers indices ==[3,5]==. Why: it is the right child of the root, so it holds the right half. (b) Its sum is $a[3]+a[4]+a[5]=3+7+4=14$. (c) One leaf per array element, so 6 leaves.

Test in the parent's fixed order.

• No overlap needs $r<lo$ or $hi<l$: here $r=4\nless 0$ and $hi=5\nless 2$. ✗
• Total overlap needs $l\le lo$ and $hi\le r$: here $l=2\nleqq 0$. ✗
• Default → ==partial overlap==. The query boundary cuts through the root's range, so we must recurse into both children.

Post-order: children first. The split points are $mid=\lfloor (lo+hi)/2\rfloor$.

• [0,5] → [0,2] and [3,5].
• [0,2] → [0,1] and [2,2].
• [0,1] → [0,0] and [1,1].
• [3,5] → [3,4] and [5,5].
• [3,4] → [3,3] and [4,4].

Now sum upward:

• [0,1] = 2+1 = 3
• [0,2] = 3 + 5 = 8 (the [0,1] sum plus leaf [2,2]=5)
• [3,4] = 3+7 = 10
• [3,5] = 10 + 4 = 14
• Root [0,5] = 8 + 14 = \mathbf{22} ✓ check: $2+1+5+3+7+4=22$.

Wanted range [1,4].

• Root [0,5]: partial → recurse.
  • [0,2]: partial ($l=1$ inside) → recurse.
    • [0,1]: partial → recurse.
      • [0,0]: no overlap ($hi=0<l=1$) → return $0$.
      • [1,1]: total ($1\le 1$ and $1\le 4$) → return $1$. stop.
    • subtotal [0,1] part $=1$.
    • [2,2]: total ($1\le 2$ and $2\le 4$) → return $5$. stop.
  • [0,2] contributes $1+5=6$.
  • [3,5]: partial → recurse.
    • [3,4]: total ($1\le 3$ and $4\le 4$) → return $10$. stop.
    • [5,5]: no overlap ($r=4<lo=5$) → return $0$.
  • [3,5] contributes $10$.
• Total $=6+10=16$. ✓ Notice [3,4] returned its whole precomputed sum — that is the $O(\log n)$ speedup in action.

The root-to-leaf path for index 4: root [0,5] → right child [3,5] (since $4>mid=2$) → left child [3,4] (since $4\le mid=4$) → leaf [4,4]. Set leaf [4,4]=1. Repair on the way up (only ancestors):

• `[3,4] = a[3]+a[4] = 3+1 = 4$(was$10$)
• `[3,5] = 4 + 4 = 8$(was$14$)
• Root `[0,5] = 8 + 8 = \mathbf{16}$(was$22$)

Unchanged: [0,2], [0,1], all left-subtree nodes, and leaf [5,5]. Only the 4 nodes on the path moved, matching $O(\log n)$.

A node expands (recurses both ways) only when it is partially overlapped — the query boundary $l$ or $r$ passes through its range. On any single level, the value $l$ can lie inside at most one node's range, and $r$ inside at most one node's range. So at most 2 nodes touch the left boundary + 2 the right boundary = 4 partial nodes per level. Everything strictly between $l$ and $r$ on that level is total overlap (returns instantly), and everything outside is no overlap. With $\lceil {\log }_{2}n\rceil$ levels, total work is $4{\log }_{2}n=O(\log n)$. This is the same "expand only at the frontier" idea behind Divide and Conquer.

Minimum is associative and defined over disjoint ranges just like sum, so the same tree shape works — only combine changes.

• [0,2] = \min(2,1,5) = \mathbf{1}
• [3,5] = \min(3,7,4) = \mathbf{3}
• Root [0,5] = \min(1,3) = \mathbf{1}

No-overlap return: the identity of min, which is $+\infty$. Why: a non-contributing node must not change the answer, and $\min (x,+\infty )=x$ for every $x$. Returning $0$ here would be wrong — $\min (x,0)$ could shrink the true minimum. This is the exact trap the parent warns about.

A prefix sum $P[k]$ is exactly the range sum over [0,k], so $P[k]=\text{query}(0,k).$ No new machinery needed — a prefix is a special range starting at index $0$. For $k=3$: $P[3]=\text{query}(0,3)=2+1+5+3=11$. (Unlike a static prefix-sum array, this one survives point updates in $O(\log n)$ — the reason segment trees beat prefix arrays under updates.)

Store a pair $(\text{value},\text{index})$ at every node.

• Leaf [i,i] stores $(a[i],i)$.
• combine$((v_L,i_L),(v_R,i_R))$:
  • if $v_L>v_R$ → take $(v_L,i_L)$;
  • if $v_R>v_L$ → take $(v_R,i_R)$;
  • if $v_L=v_R$ → take the smaller index, $(v_L,\min (i_L,i_R))$. This tie rule guarantees the leftmost maximum.
• No-overlap identity: $(-\infty ,+\infty )$ — a value that loses every comparison and an index that loses every tie.

For the array the maximum is $7$ at index $4$, so the root stores $(7,4)$. The pair is a valid combine because it is associative — a requirement for any segment-tree merge.

Each element in [l,r] needs one point update, and each point update costs $O(\log n)$. For $m=r-l+1$ elements the total is $O(m\log n)$ — and $m$ can be as large as $n$, giving $O(n\log n)$ per range update. That is worse than a plain array's $O(n)$. The fix is Lazy Propagation: store a pending "add" tag on a totally-covered node and push it down only when needed, restoring $O(\log n)$ per range update. Compare also Fenwick Tree (BIT), which handles range-add/point-query variants more compactly.

(a) $n=1$: the tree is a single node = single leaf [0,0] storing $a[0]$. Root and leaf coincide; build hits the $lo=hi$ base case immediately. tree[] of size $4\cdot 1=4$ is more than enough. (b) $l>r$ (empty range): every node reports no overlap (the condition $r<lo$ or $hi<l$ holds everywhere since $r<l\le lo$), so the query returns the identity ($0$ for sum) — the correct "empty sum". No crash. (c) [l,r] fully left of [0,n-1]: e.g. querying a range with $r<0$. The root immediately satisfies $r<lo=0$ → no overlap → returns identity $0$. The recursion never descends. ✓

A node is queried and its range lies inside [l,r] — this is the total overlap case, so we return its stored value and stop. An update to index i changes exactly the ancestors on the root-to-leaf path of i. The no-overlap return value is the identity element of combine ($0$ for sum, $+\infty$ for min). A range update via repeated point updates costs ==$O(m\log n)$, fixed by lazy propagation==.