Segment Tree — Algorhythm<br>Segment Tree

01 / The one-sentence essence<br>Build a balanced binary tree where each node holds the aggregate of a range — sum, min, max, gcd, whatever. Any range decomposes into O(log N) canonical pieces that already live as nodes, so every range query and every point update is O(log N) instead of O(N).

animationcomplexity

Problemrange sum + point updateInput[2,5,1,4,9,3,7,6]Query[1,5]Updatea[3] = 10?<br>tree[0,7][0,3][4,7][0,1][2,3][4,5][6,7][0][1][2][3][4][5][6][7]array2051124394357667Array of length 8. We'll build a binary tree where every node stores the sum of a contiguous range.

step<br>0 / 36

phase<br>build

live

0.5×1×2×<br>0 / 36

spec<br>defaultsingle-leafall-sameedge-rangemid-update

02 / The pattern signature<br># node covers [l, r]; agg = sum (or min / max / gcd / …)def build(node, l, r):if l == r: tree[node] ← arr[l]; returnm ← (l + r) // 2build(2·node, l, m); build(2·node+1, m+1, r)tree[node] ← tree[2·node] + tree[2·node+1]# query [ql, qr] — sum the canonical pieces inside itdef query(node, l, r, ql, qr):if qr or r return 0if ql ≤ l and r ≤ qr: return tree[node]m ← (l + r) // 2return query(2·node, l, m, ql, qr) + query(2·node+1, m+1, r, ql, qr)

03 / When to recognize this pattern<br>"range sum / min / max / gcd with point updates"<br>The textbook trigger. The array changes (point update), and you keep asking for the aggregate over arbitrary ranges. Prefix sum is a no-update sibling; segment tree is its mutable cousin. If updates never happen, prefix sum is simpler and tighter.

"count smaller / count of range sum"<br>The classic "inversions" family (LC 315, 327, 493) — sort or coordinate-compress the relevant key, then sweep and maintain a frequency segment tree. Each new element contributes a range-count query on what came before.

"range update + range query"<br>The grown-up variant. Add lazy propagation: each node stores a pending update for its subtree that's applied only when the recursion descends through it. Same O(log N), now both operations are ranged.

"interval / event / coverage with mutation"<br>Coordinate-compress the unique x-positions into a small array, then the segment tree maintains the live status (count, max height, etc.) at each compressed position. Skyline, rectangle coverage, calendar booking — all collapse to this.

04 / Common pitfalls<br>i.<br>Forgetting the +1 in the right half.<br>The recursion is build(2·node, l, m) and build(2·node+1, m+1, r) — the right child starts at m+1, not m. Off-by-one here gives a tree that double-counts arr[m] or silently loses it depending on which half you bias.

ii.<br>Reaching for prefix sum first, then needing updates.<br>Prefix sum is O(1) per query but O(N) per update. The moment the problem says "now change arr[i]", you have to rebuild — at which point a segment tree (or a Fenwick tree for sum specifically) wins. Recognize the mutation requirement up front.

iii.<br>Sizing the tree array wrong.<br>A safe allocation for the flat array is 4·N. The exact bound is 2·next_power_of_two(N), but allocating 4·N avoids the math and the rare case where 2N is one short. Forgetting this on a tight bound produces an out-of-range write that's painful to debug.

05 / Go practice — on LeetCode<br>Four problems, ordered by difficulty. No solutions here, by design.<br>01Range Sum Query - Mutable— LC 307medium→02Count of Smaller Numbers After Self— LC 315hard→03Count of Range Sum— LC 327hard→04Reverse Pairs— LC 493hard→