1. Introduction & Motivation
The recursive point-update, range-sum segment tree is the "hello world" of range data structures: build once, query and update in $O(\log n)$, done. But real workloads rarely stop there. A leaderboard needs to add a bonus to every player in a rank range, not just one player. A game server needs to cap thousands of values at once without touching every one of them individually. An offline analytics query needs to count how many values in a subarray fall below a threshold. A coordinate can be a 64-bit timestamp, making a dense $O(n)$ array impossible to allocate. A grid needs range sums over both rows and columns at once.
Each of these problems is answered by a specific segment tree variant, not by forcing the plain recursive version to do something it was never designed for. This lesson is a tour of six such variants: an iterative array-based rewrite that removes recursion overhead, lazy propagation for range updates, Segment Tree Beats for range chmin combined with range sum, the merge-sort tree for offline rank queries, a dynamic/implicit tree for sparse coordinate domains, and a 2D segment tree for grid queries. Every implementation here is a complete, traced-through program — not a sketch.
2. Prerequisites
This lesson assumes you are already comfortable with two structures covered elsewhere in this series and does not re-derive either of them:
- The standard recursive point-update, range-sum-query segment tree (build/update/query by splitting at the midpoint) — see the Segment Tree section of the Advanced Structures lesson, which implements it in full via LeetCode 307 (Range Sum Query — Mutable).
- The persistent segment tree, which extends the recursive version with path-copying so that every historical version of the array remains queryable — see the Persistent Segment Tree section of the Persistent Trees lesson.
If either of those two implementations is unfamiliar, read them first. Everything below assumes you already know how a segment tree recurses, and it deliberately covers only the variants that are genuinely missing from the rest of the series: iterative rewrites, lazy propagation, Segment Tree Beats, the merge-sort tree, dynamic/implicit trees, and 2D segment trees.
3. Iterative (Bottom-Up) Segment Tree
The tradeoff is a less flexible query interface: this classic construction answers range sum over a half-open interval $[l, r)$ rather than the closed $[l, r]$ interval the recursive version uses, and it is naturally suited to associative, invertible-free operations like sum, min, or max — not to arbitrary lazy range updates (that still needs the recursive form with lazy propagation, covered next). For raw point-update/range-query throughput, though, the flat-array iterative form is typically 2-3x faster in practice than the recursive version because it avoids function-call overhead entirely.
Tracing the flat array for [1, 3, 5, 7, 9, 11] (so $n=6$, tree size $12$) after the initial build:
| Index | Value | Role |
|---|---|---|
| 0 | — | unused (indices start at 1) |
| 1 | 36 | root: sum of the whole array |
| 2 | 32 | internal: sum of leaves 8, 9, 10, 11 |
| 3 | 4 | internal: sum of leaves 6, 7 |
| 4 | 12 | internal: sum of leaves 8, 9 |
| 5 | 20 | internal: sum of leaves 10, 11 |
| 6 | 1 | leaf: array[0] |
| 7 | 3 | leaf: array[1] |
| 8 | 5 | leaf: array[2] |
| 9 | 7 | leaf: array[3] |
| 10 | 9 | leaf: array[4] |
| 11 | 11 | leaf: array[5] |
Because $n=6$ is not a power of two, the internal ranges are not perfectly balanced left and right (node 2 covers four leaves while node 3 covers two) — this is expected and does not affect correctness, only the assumption that every level is "full." query(1, 4) walks $l=7, r=10$ inward: it adds tree[7]=3 (since $l$ is odd), then tree[4]=12 (since, after halving, the new $r=5$ is odd), for a total of $15$, matching $3+5+7$.
4. Lazy Propagation
lazy slot. Only "flush" that pending value into the children when a later query or update actually needs to descend past this node. This is what turns a range update from $O(n)$ (touching every affected leaf) into $O(\log n)$ (touching only the $O(\log n)$ nodes whose ranges are fully covered, plus the $O(\log n)$ nodes on the path down to them).
Without laziness, a range-add segment tree would need to update every leaf in the range, which is $O(n)$ in the worst case — no better than a plain array. Lazy propagation is the single idea that makes range updates as cheap as range queries.
Tracing update_range(2, 4, 5) then query_range(3, 3) against [1, 3, 5, 7, 9, 11]:
| Step | Node (range) | What happens | tree[node] | lazy[node] |
|---|---|---|---|---|
| 1 | node covering [2,2] | fully inside [2,4]: apply directly | 5 → 10 | 0 → 5 |
| 2 | node covering [3,4] | fully inside [2,4]: apply directly (children untouched) | 16 → 26 | 0 → 5 |
| 3 | root [0,5] | recomputed from children after both branches return | 36 → 51 | 0 |
| 4 | query(3,3) descends into node [3,4] | not fully covered by [3,3]: must push down first | 26 (unchanged) | 5 → 0 |
| 5 | leaf [3,3] (after push-down) | received the deferred +5 | 7 → 12 | 0 |
| 6 | leaf [4,4] (after push-down) | received the deferred +5 too, even though not queried | 9 → 14 | 0 |
Note step 2: the node covering [3,4] updates its own sum to 26 immediately, but its two children (values 7 and 9) are untouched until something forces a descent past that node — which is exactly what query_range(3, 3) does in step 4, since a single-index query cannot be satisfied by a node spanning two indices.
5. Segment Tree Beats
Most subtrees are skipped entirely or updated in $O(1)$; only a bounded number of nodes per update actually need to recurse. The amortized cost per chmin update is $O(\log^2 n)$ — this is proven with a potential-function argument (the number of distinct values in the array is a potential that never increases and strictly decreases every time the algorithm is forced to recurse past the trivial case), first shown by Ji Driver / the "HDU 5306" line of results. That proof is not repeated in full here; the important takeaway is that the pruning conditions above (skip when $x \ge max_1$, apply in $O(1)$ when $max_2 \le x < max_1$) are exactly what makes the amortized bound hold — get either condition wrong and the structure degrades to $O(n)$ per update.
Tracing update_chmin(0, 4, 3) against [5, 1, 4, 3, 2] (initial sum 15): the node covering index 0 alone has $max_1=5$, $max_2=-\infty$, so $x=3 > max_2$ — it applies directly, sum drops by $(5-3) \times 1 = 2$. The node covering indices 3-4 has $max_1=3$, and since $x=3 \ge max_1$, it is skipped entirely with no recursion at all. The node covering index 1 has $max_1=1$, and since $x=3 \ge max_1$, it too is skipped — index 1's value of 1 is never touched, which is exactly why query_sum(1, 1) still returns 1 afterward. Final sum: $3+1+3+3+2=12$, matching the traced result above.
6. Merge-Sort Tree
For [5, 1, 4, 3, 2], the root's sorted array is [1, 2, 3, 4, 5] (the merge of every node down to the leaves), so count_leq(0, 4, 3) resolves entirely at the root: binary search finds 3 elements $\le 3$. count_leq(1, 3, 3) decomposes into the node covering index 1 (sorted [1], contributing 1) and the node covering indices 3-4 (sorted [2, 3], contributing 1 for the value 3) — total 2, matching the subarray [1, 4, 3] having exactly two values $\le 3$.
7. Dynamic / Implicit Segment Tree
left/right child pointers (instead of array indices $2i, 2i+1$), and only create a child node the first time an update or query path actually reaches it. Untouched regions of the coordinate space never materialize any nodes at all — they implicitly contribute zero.
The time complexity per operation becomes $O(\log U)$ where $U$ is the size of the coordinate universe (not the number of elements actually present), and the space used is $O(Q \log U)$ for $Q$ updates — each update creates at most one new node per level of the tree.
Only two positions are ever updated here — index 7 and index $10^9$ — over a coordinate universe of a billion. update(7, 5) creates roughly $\log_2(10^9) \approx 30$ nodes along the path from the root to the leaf at 7; update(10^9, 3) creates another $\approx 30$ nodes down a completely different path. Everywhere else in the coordinate space, no node ever exists, and query treats a missing node as contributing zero without allocating anything.
8. 2D Segment Tree
A 2D segment tree answers range-sum (or range-min) queries over a rectangle of a grid. The idea: build an outer segment tree over rows, where every outer node — leaf or internal — holds a complete inner segment tree over columns, representing the column-wise sums of whatever row range that outer node covers. A point update touches one inner tree per outer ancestor ($O(\log R)$ of them), each update costing $O(\log C)$ — $O(\log R \cdot \log C)$ total. A rectangle query decomposes the outer range into $O(\log R)$ nodes and queries each one's inner tree over the column range, again $O(\log R \cdot \log C)$.
For the $3 \times 3$ grid above, the outer root's inner tree holds column sums [12, 15, 18] (each column summed across all three rows), so query(0, 3, 0, 3) resolves at the root: $12+15+18=45$. After update(1, 1, 50) (row 1, column 1: $5 \to 50$, delta $+45$), that same delta is added to column 1 in the inner trees of every outer ancestor of row 1's leaf — the row-1 leaf itself, and the root — which is exactly why the second query(0, 2, 0, 2) reflects the change without a full rebuild.
9. Complexity Comparison
| Variant | Time per Operation | Space | Best For |
|---|---|---|---|
| Iterative (bottom-up) | $O(\log n)$ update / query | $O(n)$ | Point update + range query with minimal per-call overhead; tight loops in performance-critical code |
| Lazy Propagation | $O(\log n)$ range update / range query | $O(n)$ | Range updates combined with range queries (range-add range-sum, range-assign range-max) |
| Segment Tree Beats | $O(\log^2 n)$ amortized update, $O(\log n)$ query | $O(n)$ | Range chmin/chmax combined with range sum, where a plain lazy tag can't represent the update |
| Merge-Sort Tree | $O(\log n)$ build per node, $O(\log^2 n)$ query | $O(n \log n)$ | Offline rank/count-in-range queries with no updates |
| Dynamic / Implicit | $O(\log U)$ update / query | $O(Q \log U)$ | Point updates over huge or sparse coordinate ranges (up to $10^9$ or more) |
| 2D Segment Tree | $O(\log R \log C)$ update / query | $O(R \cdot C)$ | 2D range-sum or range-min with point updates over a grid |
10. Applications & Alternatives
Where each variant shows up in practice
- Iterative: competitive-programming judges with tight time limits, where the constant-factor savings from removing recursion decide whether a solution passes.
- Lazy propagation: range-add leaderboards and bonus systems, interval scheduling with bulk range assignment, sweep-line algorithms in computational geometry.
- Segment Tree Beats: range chmin/chmax problems (rate-limiting a batch of counters, capping resource pools) combined with aggregate queries — the canonical reference problem is HDU 5306.
- Merge-Sort Tree: offline order-statistics queries, "$k$-th smallest in range" without updates, counting inversions restricted to a subrange.
- Dynamic/Implicit: counting inversions or coordinate-compressed events over a huge value or timestamp domain where only a handful of positions are ever touched.
- 2D: submatrix-sum queries over images or heatmaps, board-game state queries (count pieces in a rectangular region), spatial aggregation dashboards.
Alternatives worth knowing before reaching for a segment tree variant: two ordinary Fenwick (BIT) trees together can implement range-add/range-sum more simply than a lazy segment tree, at the cost of only supporting sum (not min/max/gcd). A sparse table answers static range min/max in $O(1)$ per query when there are no updates at all — cheaper than any variant here if the array never changes. A wavelet tree answers the same rank/count-in-range queries as the merge-sort tree in less space, at the cost of a trickier implementation. And when the workload needs to query every historical version of the array rather than just apply updates over huge coordinates, reach for the persistent segment tree instead of the dynamic/implicit tree described here — the two are often combined (a persistent tree over an implicit coordinate range) in the hardest competitive-programming problems.
11. Exercises
Easy
- Implement the iterative (bottom-up) segment tree for range-sum queries from scratch, using the recursive version in the Advanced Structures lesson as your reference for what the correct answers should be. Verify your iterative version returns the same results for at least five random range queries.
- Modify your iterative tree to support range-min instead of range-sum, and confirm it still passes the same five queries (adjusted for the new operation).
Medium
- Build a lazy-propagation segment tree over the array
[10, 4, 8, 2, 6, 12, 1]. Applyupdate_range(1, 5, 3)(add 3 to indices 1 through 5), then query the sum of indices 0 through 6. By hand, trace which nodes apply the update directly versus which ones only see it after a forced push-down. - Extend the same structure to support range assignment (set every element in $[l, r]$ to a fixed value) instead of range add, and explain why the lazy tag now needs a "has a pending assignment" flag in addition to a value.
Hard
- Using the Merge-Sort Tree, implement a function that counts how many elements in $[l, r]$ are $\le x$ for an array of at least 12 elements, and verify it against a brute-force linear scan for 10 random $(l, r, x)$ triples.
- Implement range chmax (for every index in $[l, r]$, set $arr[i] = \max(arr[i], x)$) combined with range-sum queries, as the mirror image of Segment Tree Beats' range chmin. You will need to track the minimum value, the second-minimum, and a count-of-minimum per node instead of the maximum-side statistics used in this lesson — every pruning condition flips accordingly.
Review rhythm: tomorrow, re-derive the lazy-propagation push-down order from memory (apply-then-clear, always before recursing past a node) without looking back at the code. Next week, re-implement Segment Tree Beats' three-way branch (skip / apply-in-O(1) / recurse) from the core insight alone. Several weeks later, work through the mastery challenge above and check whether your combined design matches a real "persistent + implicit" or "beats + lazy" structure you find in a competitive-programming reference.
12. Summary Cheat Sheet
- Iterative segment tree: flat array of size $2n$, leaves at $[n, 2n)$, parent of $i$ is $\lfloor i/2 \rfloor$ — removes recursion overhead, but typically uses half-open query ranges.
- Lazy propagation: apply a pending update to a node's own aggregate immediately, defer pushing it to children until forced to descend past that node — turns range updates from $O(n)$ into $O(\log n)$.
- Segment Tree Beats: track max, second-max, and count-of-max per node to skip subtrees a chmin update provably can't affect, or fix them in $O(1)$ — $O(\log^2 n)$ amortized via a potential-function argument.
- Merge-Sort Tree: each node stores a sorted copy of its subarray, enabling $O(\log^2 n)$ count-$\le x$-in-range queries via per-level binary search; no updates in the basic form.
- Dynamic/implicit segment tree: allocate nodes lazily via left/right pointers instead of array indices, so a huge or sparse coordinate universe costs only $O(\log U)$ per touched position.
- 2D segment tree: an outer segment tree of inner segment trees, giving $O(\log R \log C)$ rectangle queries at the cost of $O(R \cdot C)$ space.
- Always know which of the two prerequisite structures — the plain recursive tree or the persistent tree — a new requirement actually calls for before reaching for a more exotic variant.