Segment Trees in Depth
Why this exists
Prefix sums answer "sum of a[l..r]" in after an build, and collapse the moment the array changes: one update invalidates up to prefix values. A plain array has the opposite profile: update, query. Real workloads interleave the two. A leaderboard changes scores and asks for ranks; a booking system reserves seats and asks for the first block of free ones; a monitoring system appends samples and asks for the maximum over a window; a contest problem gives updates and queries and a one-second limit. Anything per operation is steps. You need both operations in .
A segment tree gets there by precomputing the answer not for prefixes but for a hierarchy of blocks: the whole array, its two halves, their halves, and so on down to single elements. Any range is the disjoint union of of those blocks, and any single element lies in exactly one block per level, so a point update touches precomputed answers. The only thing the structure needs from the operation is associativity — which is why the same skeleton answers sums, minimums, GCDs, products of matrices, and "maximum subarray sum inside the range", and why with lazy propagation it also supports range updates.
The name comes from computational geometry. Jon Bentley introduced the segment tree in 1977 (in his unpublished notes "Solutions to Klee's rectangle problems") to compute the area of a union of rectangles with a sweep line; there, each node stores the set of intervals that cover its segment. The competitive-programming segment tree described here, storing an aggregate per node, is a descendant of that idea and of the "binary indexed" aggregation trees in general; the two meanings share a shape but not a purpose, so be aware of the ambiguity when reading older literature. The short segment tree section of the Trees overview and the Advanced Data Structures page show the basic recursive version. This lesson derives why it works, proves its bounds, gives the fast iterative form, and then walks through lazy propagation, tree descent, persistence, segment tree beats and sparse trees.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| Range sum / min / max / gcd with point updates interleaved | Point-update segment tree (or Fenwick for sums) |
| "add v to every element in [l, r]" and "sum / min of [l, r]" interleaved | Lazy propagation with an add tag |
| "set every element in [l, r] to v" | Lazy propagation with an assign tag (compose with add carefully) |
| "maximum subarray sum within [l, r]", "longest run of 1s in a range" | Custom node (sum, best prefix, best suffix, best) and a merge |
| "first position ≥ l whose value is ≥ x", "first free block of size k" | Walk down a max segment tree |
| "k-th one / k-th remaining element", "remove the element at position k" | Count tree + descent by counts |
| "k-th smallest in a[l..r]", "queries on old versions" | Persistent segment tree (path copying) |
| Coordinates up to but only operations | Coordinate compression, or a dynamic (sparse) segment tree |
| "a[i] = min(a[i], x) over a range", with sum queries | Segment tree beats (Ji's chmin) |
| Applying a sequence of transformations to ranges, order matters | Non-commutative monoid (matrices, function composition) |
| Union area / covered length of intervals under a sweep line | Segment tree with cover counts (Bentley's original use) |
| Only prefix sums with point updates, memory or code size matters | Fenwick tree instead |
| Static array, idempotent query (min/max/gcd) | Sparse table — query, no updates (see the sparse tables lesson) |
The meta-trigger: range queries and updates interleaved, on an associative operation. If there are no updates, something simpler (prefix sums, sparse table) probably wins. If the operation is not associative, no segment tree can help.
Intuition & first principles
Start with the question: what should be precomputed so that any range answer can be assembled quickly, and so that any single change invalidates few precomputed values? Prefix sums precompute values, each depending on up to elements; that is why one update breaks so many. We want precomputed values that each depend on a block of elements, such that every element lies in few blocks and every range is covered by few blocks.
The dyadic blocks are the answer. Level 0 is the whole array. Level 1 splits it into two halves. Level has blocks of size about . There are about levels, and blocks in total (a full binary tree with leaves). Each element is in exactly one block per level — about blocks. Each range can be written as a disjoint union of blocks using at most two blocks per level (shown in the correctness section). Store the aggregate of each block in a tree node, and both operations cost .
Why associativity is the only requirement: a query combines block answers in left-to-right order, and those blocks were themselves built by combining their halves. For the final result to be the same as combining the elements one by one, regrouping must not matter: . Formally the node values must form a monoid: a set with an associative operation and an identity element (so that empty parts of a query contribute nothing). Commutativity is not required, which is what lets segment trees compose matrices and functions — but it means the implementation must keep left and right parts in order.
Contrast with Fenwick trees: those additionally need an inverse (to subtract one prefix from another) for range queries, which is why a Fenwick tree cannot answer range minimum over arbitrary ranges and a segment tree can.
Mechanics
Structure and build
Take a = [5, 3, 7, 9, 6, 4, 1, 2]. Node 1 is the root covering ; node covering has children covering and covering , with . This is the heap numbering from heaps, which needs no child pointers.
flowchart TD
N1["1: [0,7] = 37"] --> N2["2: [0,3] = 24"]
N1 --> N3["3: [4,7] = 13"]
N2 --> N4["4: [0,1] = 8"]
N2 --> N5["5: [2,3] = 16"]
N3 --> N6["6: [4,5] = 10"]
N3 --> N7["7: [6,7] = 3"]
N4 --> L0["[0] 5"]
N4 --> L1["[1] 3"]
N5 --> L2["[2] 7"]
N5 --> L3["[3] 9"]
N6 --> L4["[4] 6"]
N6 --> L5["[5] 4"]
N7 --> L6["[6] 1"]
N7 --> L7["[7] 2"]
The build is a post-order recursion: build both children, then set t[v] = t[2v] + t[2v+1]. Each node is computed once: .
| Level (depth) | Nodes computed | Values |
|---|---|---|
| 3 (leaves) | [0] … [7] | 5, 3, 7, 9, 6, 4, 1, 2 |
| 2 | [0,1], [2,3], [4,5], [6,7] | 8, 16, 10, 3 |
| 1 | [0,3], [4,7] | 24, 13 |
| 0 | [0,7] | 37 |
Range query, recursively
To answer sum(l, r), start at the root and classify each node against the query:
- disjoint ( or ): contributes the identity (0 for sums); do not descend;
- fully covered ( and ): contributes its stored value; do not descend;
- partial overlap: recurse into both children and combine.
flowchart TD
Q["visit node [tl, tr]"] --> D{"disjoint from [l, r]?"}
D -->|"yes"| E["return identity"]
D -->|"no"| C{"inside [l, r]?"}
C -->|"yes"| S["return t[v]"]
C -->|"no"| R["recurse left and right<br/>return combine(left, right)"]
Trace: sum over [2, 6]
Generated by scripts/traces/segment_tree_query.py — the same run as the visualizer. The answer should be .
| Step | Node (segment) | Classification | Action | Running sum |
|---|---|---|---|---|
| 1 | 1: [0,7] | partial | recurse | 0 |
| 2 | 2: [0,3] | partial | recurse | 0 |
| 3 | 4: [0,1] | disjoint | return 0 | 0 |
| 4 | 5: [2,3] | covered | take 16 | 16 |
| 5 | 3: [4,7] | partial | recurse | 16 |
| 6 | 6: [4,5] | covered | take 10 | 26 |
| 7 | 7: [6,7] | partial | recurse | 26 |
| 8 | [6] | covered | take 1 | 27 |
| 9 | [7] | disjoint | return 0 | 27 |
Nine of fifteen nodes were touched; three of them — [2,3], [4,5] and [6] — form the canonical decomposition of . The partial nodes ([0,7], [0,3], [4,7], [6,7]) are exactly the ancestors of the two boundary leaves and that are not themselves covered. That observation is the whole complexity proof.
Point update
To set a[3] = 0, descend to leaf 3, overwrite it, and recompute every ancestor on the way back up. With the iterative layout below (leaves at t[n + i]), the path is leaf index 11 and its ancestors:
| Node index | Segment | New value | Computed as |
|---|---|---|---|
| 11 | [3] | 0 | set |
| 5 | [2,3] | 7 | 7 + 0 |
| 2 | [0,3] | 15 | 8 + 7 |
| 1 | [0,7] | 28 | 15 + 13 |
Exactly one node per level changed: writes.
The iterative (bottom-up) segment tree
Recursion is clean but slow: function calls, bounds tracking, and a array. Al.Cash's Codeforces blog post "Efficient and easy segment trees" (2015) popularized a non-recursive layout that is shorter, uses exactly memory, and runs several times faster in practice:
- leaves live at
t[n] … t[2n-1](a[i]att[n + i]); - internal node
i(for1 ≤ i < n) ist[i] = t[2i] ∘ t[2i+1], computed fori = n-1down to1; - update
p: sett[p + n], then repeatedly move to the parentp >>= 1and recompute it from its two children; - query on the half-open range : set
l += n,r += n, and whilel < r: iflis odd it is a right child whose parent would stick out past the left boundary, so taket[l]and steplright; ifris odd, the noder - 1is a left child whose parent sticks out past the right boundary, so taket[r - 1]; then move both up a level.
Trace: sum[2, 7) (the same range inclusive) on the eight-element array, so l = 10, r = 15 initially. t = [_, 37, 24, 13, 8, 16, 10, 3, 5, 3, 7, 9, 6, 4, 1, 2].
| Round | l | r | Left boundary | Right boundary | Result |
|---|---|---|---|---|---|
| 1 | 10 | 15 | 10 even: skip | 15 odd: r = 14, take t[14] = 1 (a[6]) | 1 |
| 2 | 5 | 7 | 5 odd: take t[5] = 16 ([2,3]), l = 6 | 7 odd: r = 6, take t[6] = 10 ([4,5]) | 27 |
| 3 | 3 | 3 | l = r: stop | 27 |
The same three blocks as the recursive version, found bottom-up in two rounds. For a non-commutative operation, keep two accumulators: resl = resl ∘ t[l] on the left and resr = t[r] ∘ resr on the right, and return resl ∘ resr.
A subtle and surprising property: this layout works for any , not only powers of two. For that is not a power of two, some internal nodes cover "wrapped" or meaningless combinations, but the query loop provably never uses them — a node is taken only when it lies entirely inside . Al.Cash's post explains why; the randomized tests in the implementation below check it, including for a non-commutative operation on .
Lazy propagation
Now support "add to every element of " alongside range-sum queries. Updating every leaf in the range is . The fix is to apply the update to the canonical nodes of — exactly the nodes a query would take — and record at each a pending tag: "every element in my segment still owes to my descendants". A node's own value is updated immediately (its sum rises by ), so queries that stop at it are correct. Descendants are updated only when some later operation needs to go below that node.
The discipline has two functions, and getting it right is the whole difficulty:
- apply(v, tag): make node
vreflecttag— update its value and composetaginto its pending tag. For add/sum:t[v] += x * len(v),lz[v] += x. - push(v): hand
v's pending tag to both children withapply, then clear it. Callpush(v)before descending fromvin any operation, update or query.
And after recursing into children in an update, pull: recompute t[v] from the children.
Trace on a = [5, 3, 7, 9, 6, 4, 1, 2]: first add(1, 5, +2), then sum(3, 4). Expected array afterwards [5, 5, 9, 11, 8, 6, 1, 2], so sum(3, 4) = 11 + 8 = 19.
| Step | Operation | Node | Situation | Action | Node value / tag after |
|---|---|---|---|---|---|
| 1 | add | [0,7] | partial | push (no tag), recurse | — |
| 2 | add | [0,3] | partial | recurse | — |
| 3 | add | [0,1] | partial | recurse | — |
| 4 | add | [0] | disjoint | return | 5 / 0 |
| 5 | add | [1] | covered | apply +2 | 5 / 2 |
| 6 | add | [0,1] | pull | 5 + 5 | 10 / 0 |
| 7 | add | [2,3] | covered | apply +2: 16 + 2·2 | 20 / 2 |
| 8 | add | [0,3] | pull | 10 + 20 | 30 / 0 |
| 9 | add | [4,7] | partial | recurse | — |
| 10 | add | [4,5] | covered | apply +2: 10 + 2·2 | 14 / 2 |
| 11 | add | [6,7] | disjoint | return | 3 / 0 |
| 12 | add | [4,7] | pull | 14 + 3 | 17 / 0 |
| 13 | add | [0,7] | pull | 30 + 17 | 47 / 0 |
| 14 | sum(3,4) | [0,7], [0,3] | partial | push (no tags), recurse | — |
| 15 | sum(3,4) | [0,1] | disjoint | return 0 | — |
| 16 | sum(3,4) | [2,3] | partial, has tag 2 | push: [2] 7→9, [3] 9→11, clear tag | 20 / 0 |
| 17 | sum(3,4) | [3] | covered | take 11 | — |
| 18 | sum(3,4) | [4,7] | partial | recurse | — |
| 19 | sum(3,4) | [4,5] | partial, has tag 2 | push: [4] 6→8, [5] 4→6, clear tag | 14 / 0 |
| 20 | sum(3,4) | [4] | covered | take 8; [5] and [6,7] disjoint | total 19 |
Note step 7: [2,3] absorbed the update for two elements without touching them. They were updated at step 16, only because a query needed to split that node — and if no one ever had, they would never have been.
Composing tags: range assign plus range add
With several update types, a tag must represent the composition of any sequence of updates, in a constant-size form. For "assign " and "add ", every sequence collapses to "optionally assign , then add ": an assign wipes everything before it, and adds accumulate. So the tag is a pair (s or none, d) and composition of an older tag followed by a newer is
Applying a tag to a node of length : if is set, sum = s·k; then sum += d·k. The order inside apply must match the order inside the tag's meaning. Most lazy bugs are composition bugs: applying a new assign without clearing the old add, or composing in the wrong order. The general rule: tags must form a monoid acting on node values, and apply must satisfy .
Walking down the tree
A segment tree is also a search structure. Because each node knows the aggregate of its subtree, you can descend from the root and decide at each node which child holds the answer, in , instead of binary-searching over queries in .
- First index with (max tree): descend; skip any node whose segment ends before or whose max is below ; otherwise try the left child first, then the right. On
[5, 3, 7, 9, 6, 4, 1, 2], the first value is at index 3; the first value at or after index 4 is at index 4; at or after index 5 none exists. - k-th one (count tree over a 0/1 array): at each node, if count of the left child go left, else subtract that count and go right. This answers "remove the k-th remaining element" (Josephus-style problems, CSES List Removals) and is an order-statistic tree over a bounded universe.
- Prefix of a given sum: find the smallest with for non-negative — the same descent on a sum tree. This is how prioritized experience replay samples proportionally to priority (below).
The descent with a left bound costs : the nodes that straddle lie on one root-to-leaf path; any node fully to the right of either fails the max test immediately or contains the answer, and the first such node is entered and descended without backtracking.
Persistent segment trees
A persistent structure keeps every past version queryable. For a segment tree this is cheap: a point update changes only the nodes on one root-to-leaf path, so instead of modifying them, copy them, with the copies pointing to the unchanged siblings of the old version. Each update creates new nodes and a new root; old roots still describe old versions exactly. This is path copying (Driscoll, Sarnak, Sleator and Tarjan, "Making Data Structures Persistent", JCSS 1989, survey the general technique).
flowchart TD
R0["root v0: count 2"] --> A0["[0,1]: 1"]
R0 --> B0["[2,3]: 1"]
R1["root v1: count 3"] --> A0
R1 --> B1["[2,3]: 2 (copy)"]
B1 --> C1["[3]: 1 (copy)"]
B0 --> C0["[2]: 1"]
B1 --> C0
The classic application is k-th smallest in a subarray . Compress values to ranks . Version is a count tree over ranks containing (version 0 is empty). Then the multiset of is "version minus version ", and the count of elements of in any rank range is a difference of two node counts. Descend both versions in lockstep: if go left, else subtract and go right. per query, memory. On our array, the sorted values of are [1, 4, 6, 7, 9], and the implementation below checks all five order statistics against that.
Segment tree beats
Some range updates do not admit a constant-size lazy tag. " for " (range chmin) with range-sum queries is the standard example: how much the sum drops depends on how many elements exceed and by how much, which a tag cannot know.
Ji Ruyi's segment tree beats (presented in the 2016 Chinese IOI team papers and popularized in English by the Codeforces blog "A simple introduction to 'Segment tree beats'" by user jiry_2) handles it by storing at each node the maximum, the strict second maximum and the count of the maximum, plus the sum. For a chmin with value at a node:
- if : nothing to do, stop;
- if : only the maximal elements change, all to ; the sum drops by ; record the new max as the tag (children whose max exceeds the parent's are clipped when pushed), stop;
- otherwise (): recurse into both children and pull.
The third case looks like it could make every chmin cost , but it cannot happen often: each time it occurs at a node, the number of distinct values in that node's segment strictly decreases (the max and second max merge). A potential argument over the total number of distinct values per node bounds the total work by for chmin plus sum queries. With range add mixed in, Ji proves . The implementation below is a direct transcription, checked against brute force.
Dynamic (sparse) segment trees
When indices range over but there are only operations, a full tree is impossible. Two fixes:
- Coordinate compression (offline): collect every index that will ever be touched, sort, map to , and build over points. Fast and simple when all operations are known in advance.
- Dynamic segment tree (online): start with only a root, and create a child the first time an operation needs to go below a node. A missing child means "all identity". Each operation creates at most nodes for universe size , so memory is — for and , about nodes at most. Lazy propagation works too (create children when pushing).
2D segment trees
A segment tree whose nodes are segment trees answers rectangle queries in with point updates; memory is for dense grids, with dynamic inner trees. Range updates in 2D are much harder (lazy tags do not push cleanly across the outer dimension). Alternatives: a 2D Fenwick tree for sums, a merge-sort tree (each node stores its sorted segment) for offline counting in , quadtrees and k-d trees for geometric data (see spatial trees).
The ladder: brute force → better → optimal
Running problem: an array of numbers, operations, each either "set " or "sum of ". Take .
Rung 1: plain array
Update , query . Worst case . Too slow by a factor of about a hundred.
Rung 2: prefix sums, rebuilt on update
Query , update (every prefix after shifts). Same worst case in the other direction. The two rungs are mirror images: each makes one operation free by making the other linear.
Rung 3: sqrt decomposition
Split into blocks of size and keep each block's sum. Update: fix the element and its block sum, . Query: whole blocks in the middle plus partial blocks at the ends, . Total — feasible in C++, tight elsewhere. Sqrt decomposition is extremely flexible (it handles operations a segment tree cannot) and is covered in the sparse tables and sqrt decomposition lesson.
Rung 4: segment tree
Blocks of every size , organized as a tree. Both operations : about 18 levels for , so roughly node visits for the iterative version. Up to constants, nothing can do better: Fredman and Saks (1989) proved an cell-probe lower bound per operation for dynamic prefix sums, and Pătrașcu and Demaine (2004) tightened it to .
Rung 5 (sums only): Fenwick tree
Same , half the memory of the iterative tree, smaller constant. But only for invertible operations and simpler update types. See Fenwick trees.
| Approach | Update | Query | Memory | Operations supported |
|---|---|---|---|---|
| Plain array | Anything | |||
| Prefix sums | Invertible (sum, xor) | |||
| Sqrt decomposition | or | Almost anything decomposable | ||
| Segment tree (recursive) | Any monoid; lazy range updates | |||
| Segment tree (iterative) | Any monoid; lazy is possible but fiddlier | |||
| Fenwick tree | Invertible operations; limited range updates |
Correctness
Why is enough (and is not, recursively)
With the recursive layout, the root is node 1 and a node at depth has index in . A segment of length splits into halves of length and , so a node at depth covers at most elements, and leaves appear by depth . Every index is therefore below . Since (because ), we get . Hence an array of size always suffices.
It is also close to necessary: the maximum index really approaches when is slightly above a power of two. Measured by script: uses index 9; uses index 253 (2.53n); uses index 16257 (about 3.91n). So is not enough for the recursive layout, even though only nodes exist — the heap numbering leaves holes. The iterative layout has no holes and uses exactly .
Query cost: at most four nodes per level
Claim. The recursive query visits at most 4 nodes per level and takes at most 2 covering nodes per level, so it visits nodes.
Proof. At any level, the segments of that level's nodes are disjoint and ordered. Call a node at that level partial if it overlaps without being contained in it. A partial node must contain or strictly inside or at its edge with part sticking out — that is, it contains position and , or and . Since segments at one level are disjoint, at most one node contains the pair and at most one contains . So at most 2 partial nodes per level. Only partial nodes recurse, and each has 2 children, so at most 4 nodes are visited at the next level. Covered nodes taken at a level are children of partial nodes of the previous level, at most 4 — and a sharper argument shows at most 2 (a partial node containing can contribute a covered node only from its right child, one containing only from its left). With about levels, the query visits at most nodes and returns at most covering blocks.
Measured by exhaustive search over all ranges: for the worst query visits 11 nodes and uses 4 covering blocks; for , 15 nodes and 6 blocks.
Correctness of the returned value. By induction on the height of the node: a disjoint node returns , which is the aggregate of the empty intersection; a covered node returns its stored aggregate, which by the build/update invariant equals the aggregate of its whole segment = the intersection; a partial node returns , which by induction is , and by associativity that equals the aggregate of the concatenation, i.e. of , in order.
Point update
Invariant: every node stores the aggregate of its segment. A point update changes the aggregate of exactly the segments that contain — one per level, the root-to-leaf path. The update rewrites the leaf and recomputes each ancestor bottom-up from its children; each recomputed value is correct because its children are correct (the child on the path was just fixed, the other was never affected). Every other node's segment does not contain , so its stored value remains correct.
Lazy propagation
Invariant. For every node : t[v] equals the true aggregate of 's segment after applying all pending tags of 's strict ancestors. Equivalently, t[v] already includes 's own tag, and the tag at describes updates that 's descendants have not yet received.
apply(v, f)keeps it: it updatest[v]by (valid only because applies uniformly to the whole segment, which is true for the operations considered) and composes intolz[v]so the descendants will receive it later.push(v)keeps it: it moveslz[v]into both children viaapply, so the children's values now include that tag, and clearslz[v]. After a push, no ancestor-of-child tag is pending at , and the children's invariant holds without reference to .- Every operation pushes at a node before descending past it, so whenever we read or modify a child, all tags of its ancestors on the current path have been pushed — the child's stored value is its true value.
- An update that covers a node calls
applythere, and pulls ancestors afterwards, which recomputes them from children that are now correct.
A query that stops at a covered node returns t[v], which by the invariant (and since all ancestors on the path were pushed) is the true aggregate.
The proof also tells you what can go wrong: any read of a child without pushing first reads a stale value, and any apply that is not a valid "uniform update on a whole segment" (like chmin) breaks the first bullet — which is exactly why segment tree beats needs extra information to know when a uniform update is valid.
Complexity
| Operation | Recursive | Iterative | Notes |
|---|---|---|---|
| Build | combines | ||
| Point update | one node per level | ||
| Range query | ≤ 4 visits and ≤ 2 blocks per level | ||
| Range update (lazy) | (with push from the top) | requires constant-size composable tags | |
| Walk down (first ≥ x, k-th) | with care | ||
| Persistent update | time and new nodes | — | each version space |
| Beats chmin + sum | amortized | — | amortized with range add |
| Space | values (+ tags) | values | sparse: |
If combining two node values costs (for example for matrices), multiply every time bound by .
Constants and cache. The iterative version touches nodes with no function calls and its upper levels stay in L1/L2 cache, which is why it typically runs a few times faster than the recursive version. The recursive version's array of 64-bit sums for is 32 MB (64 MB with lazy tags), versus 16 MB for the iterative one; once the tree exceeds cache, each level is a likely cache miss near the leaves. A Fenwick tree halves memory again and its loop body is a single add and a bit trick, so for plain sums it is usually the fastest of the three.
Implementation
Iterative segment tree: point update, range sum
Half-open queries , as in Al.Cash's post. Each version checks the trace values above and then runs 2,000 random operations against a brute-force array of size 37 (not a power of two), using the same MINSTD pseudo-random generator in every language.
class SegmentTree:
"""Bottom-up segment tree: point assignment, sum over [l, r)."""
def __init__(self, a: list[int]) -> None:
self.n = n = len(a)
self.t = [0] * n + list(a)
for i in range(n - 1, 0, -1):
self.t[i] = self.t[2 * i] + self.t[2 * i + 1]
def set(self, p: int, value: int) -> None:
t = self.t
p += self.n
t[p] = value
while p > 1:
p >>= 1
t[p] = t[2 * p] + t[2 * p + 1]
def query(self, l: int, r: int) -> int:
t, res = self.t, 0
l += self.n
r += self.n
while l < r:
if l & 1:
res += t[l]
l += 1
if r & 1:
r -= 1
res += t[r]
l >>= 1
r >>= 1
return res
class Minstd:
def __init__(self, seed: int) -> None:
self.s = seed
def next(self) -> int:
self.s = self.s * 48271 % 2147483647
return self.s
if __name__ == "__main__":
st = SegmentTree([5, 3, 7, 9, 6, 4, 1, 2])
assert st.query(2, 7) == 27 and st.query(0, 8) == 37
st.set(3, 0)
assert st.query(0, 8) == 28 and st.query(2, 7) == 18 and st.query(3, 4) == 0
rng, n = Minstd(42), 37
brute = [rng.next() % 1000 for _ in range(n)]
st = SegmentTree(brute)
for _ in range(2000):
if rng.next() % 2 == 0:
p, v = rng.next() % n, rng.next() % 1000
st.set(p, v)
brute[p] = v
else:
l, r = rng.next() % n, rng.next() % n
if l > r:
l, r = r, l
assert st.query(l, r + 1) == sum(brute[l:r + 1])
assert SegmentTree([42]).query(0, 1) == 42
print("iterative segment tree ok")
public class SegmentTree {
private final int n;
private final long[] t;
SegmentTree(long[] a) {
n = a.length;
t = new long[2 * n];
System.arraycopy(a, 0, t, n, n);
for (int i = n - 1; i > 0; i--) t[i] = t[2 * i] + t[2 * i + 1];
}
void set(int p, long value) {
for (t[p += n] = value; p > 1; p >>= 1) t[p >> 1] = t[p] + t[p ^ 1];
}
long query(int l, int r) { // [l, r)
long res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if ((l & 1) == 1) res += t[l++];
if ((r & 1) == 1) res += t[--r];
}
return res;
}
static long seed = 42;
static long next() {
seed = seed * 48271 % 2147483647L;
return seed;
}
private static void check(boolean cond, String msg) {
if (!cond) throw new AssertionError(msg);
}
public static void main(String[] args) {
SegmentTree st = new SegmentTree(new long[] {5, 3, 7, 9, 6, 4, 1, 2});
check(st.query(2, 7) == 27 && st.query(0, 8) == 37, "trace");
st.set(3, 0);
check(st.query(0, 8) == 28 && st.query(2, 7) == 18 && st.query(3, 4) == 0, "update");
int n = 37;
long[] brute = new long[n];
for (int i = 0; i < n; i++) brute[i] = next() % 1000;
st = new SegmentTree(brute.clone());
for (int it = 0; it < 2000; it++) {
if (next() % 2 == 0) {
int p = (int) (next() % n);
long v = next() % 1000;
st.set(p, v);
brute[p] = v;
} else {
int l = (int) (next() % n), r = (int) (next() % n);
if (l > r) { int tmp = l; l = r; r = tmp; }
long expect = 0;
for (int i = l; i <= r; i++) expect += brute[i];
check(st.query(l, r + 1) == expect, "random");
}
}
check(new SegmentTree(new long[] {42}).query(0, 1) == 42, "single");
System.out.println("iterative segment tree ok");
}
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>
class SegmentTree {
int n;
std::vector<long long> t;
public:
explicit SegmentTree(const std::vector<long long>& a)
: n(static_cast<int>(a.size())), t(2 * a.size()) {
for (int i = 0; i < n; ++i) t[n + i] = a[i];
for (int i = n - 1; i > 0; --i) t[i] = t[2 * i] + t[2 * i + 1];
}
void set(int p, long long value) {
for (t[p += n] = value; p > 1; p >>= 1) t[p >> 1] = t[p] + t[p ^ 1];
}
long long query(int l, int r) const { // [l, r)
long long res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) res += t[l++];
if (r & 1) res += t[--r];
}
return res;
}
};
std::int64_t seed = 42;
std::int64_t next() {
seed = seed * 48271 % 2147483647LL;
return seed;
}
int main() {
SegmentTree st({5, 3, 7, 9, 6, 4, 1, 2});
assert(st.query(2, 7) == 27 && st.query(0, 8) == 37);
st.set(3, 0);
assert(st.query(0, 8) == 28 && st.query(2, 7) == 18 && st.query(3, 4) == 0);
const int n = 37;
std::vector<long long> brute(n);
for (auto& x : brute) x = next() % 1000;
SegmentTree rt(brute);
for (int it = 0; it < 2000; ++it) {
if (next() % 2 == 0) {
int p = static_cast<int>(next() % n);
long long v = next() % 1000;
rt.set(p, v);
brute[p] = v;
} else {
int l = static_cast<int>(next() % n), r = static_cast<int>(next() % n);
if (l > r) std::swap(l, r);
long long expect = 0;
for (int i = l; i <= r; ++i) expect += brute[i];
assert(rt.query(l, r + 1) == expect);
}
}
assert(SegmentTree({42}).query(0, 1) == 42);
std::cout << "iterative segment tree ok\n";
return 0;
}
class SegmentTree {
private n: number;
private t: number[];
constructor(a: number[]) {
this.n = a.length;
this.t = new Array<number>(this.n).fill(0).concat(a);
for (let i = this.n - 1; i > 0; i--) this.t[i] = this.t[2 * i] + this.t[2 * i + 1];
}
set(p: number, value: number): void {
p += this.n;
this.t[p] = value;
for (; p > 1; p >>= 1) this.t[p >> 1] = this.t[p] + this.t[p ^ 1];
}
query(l: number, r: number): number {
// [l, r)
let res = 0;
for (l += this.n, r += this.n; l < r; l >>= 1, r >>= 1) {
if (l & 1) res += this.t[l++];
if (r & 1) res += this.t[--r];
}
return res;
}
}
let seed = 42;
function next(): number {
seed = (seed * 48271) % 2147483647;
return seed;
}
function check(cond: boolean, msg: string): void {
if (!cond) throw new Error(msg);
}
const st = new SegmentTree([5, 3, 7, 9, 6, 4, 1, 2]);
check(st.query(2, 7) === 27 && st.query(0, 8) === 37, "trace");
st.set(3, 0);
check(st.query(0, 8) === 28 && st.query(2, 7) === 18 && st.query(3, 4) === 0, "update");
const n = 37;
const brute: number[] = [];
for (let i = 0; i < n; i++) brute.push(next() % 1000);
const rt = new SegmentTree(brute.slice());
for (let it = 0; it < 2000; it++) {
if (next() % 2 === 0) {
const p = next() % n;
const v = next() % 1000;
rt.set(p, v);
brute[p] = v;
} else {
let l = next() % n;
let r = next() % n;
if (l > r) [l, r] = [r, l];
let expect = 0;
for (let i = l; i <= r; i++) expect += brute[i];
check(rt.query(l, r + 1) === expect, "random");
}
}
check(new SegmentTree([42]).query(0, 1) === 42, "single");
console.log("iterative segment tree ok");
Recursive segment tree with lazy propagation: range add, range sum
Inclusive bounds, heap numbering, arrays of size . The tests replay the lazy trace (add(1, 5, 2) then three sums) and 2,000 random range adds and range sums against brute force.
class LazySegTree:
"""Range add, range sum, inclusive bounds."""
def __init__(self, a: list[int]) -> None:
self.n = len(a)
self.t = [0] * (4 * self.n)
self.lz = [0] * (4 * self.n)
self._build(a, 1, 0, self.n - 1)
def _build(self, a: list[int], v: int, tl: int, tr: int) -> None:
if tl == tr:
self.t[v] = a[tl]
return
tm = (tl + tr) // 2
self._build(a, 2 * v, tl, tm)
self._build(a, 2 * v + 1, tm + 1, tr)
self.t[v] = self.t[2 * v] + self.t[2 * v + 1]
def _apply(self, v: int, tl: int, tr: int, x: int) -> None:
self.t[v] += x * (tr - tl + 1)
self.lz[v] += x
def _push(self, v: int, tl: int, tr: int) -> None:
if self.lz[v]:
tm = (tl + tr) // 2
self._apply(2 * v, tl, tm, self.lz[v])
self._apply(2 * v + 1, tm + 1, tr, self.lz[v])
self.lz[v] = 0
def add(self, l: int, r: int, x: int) -> None:
self._add(1, 0, self.n - 1, l, r, x)
def _add(self, v: int, tl: int, tr: int, l: int, r: int, x: int) -> None:
if r < tl or tr < l:
return
if l <= tl and tr <= r:
self._apply(v, tl, tr, x)
return
self._push(v, tl, tr)
tm = (tl + tr) // 2
self._add(2 * v, tl, tm, l, r, x)
self._add(2 * v + 1, tm + 1, tr, l, r, x)
self.t[v] = self.t[2 * v] + self.t[2 * v + 1]
def sum(self, l: int, r: int) -> int:
return self._sum(1, 0, self.n - 1, l, r)
def _sum(self, v: int, tl: int, tr: int, l: int, r: int) -> int:
if r < tl or tr < l:
return 0
if l <= tl and tr <= r:
return self.t[v]
self._push(v, tl, tr)
tm = (tl + tr) // 2
return self._sum(2 * v, tl, tm, l, r) + self._sum(2 * v + 1, tm + 1, tr, l, r)
def minstd(seed: int):
while True:
seed = seed * 48271 % 2147483647
yield seed
if __name__ == "__main__":
st = LazySegTree([5, 3, 7, 9, 6, 4, 1, 2])
st.add(1, 5, 2)
assert st.sum(0, 7) == 47 and st.sum(0, 3) == 30 and st.sum(3, 4) == 19
rng, n = minstd(7), 37
brute = [next(rng) % 100 for _ in range(n)]
st = LazySegTree(brute)
for _ in range(2000):
op, l, r = next(rng) % 2, next(rng) % n, next(rng) % n
if l > r:
l, r = r, l
if op == 0:
x = next(rng) % 50
st.add(l, r, x)
for i in range(l, r + 1):
brute[i] += x
else:
assert st.sum(l, r) == sum(brute[l:r + 1])
print("lazy segment tree ok")
public class LazySegTree {
private final int n;
private final long[] t, lz;
LazySegTree(long[] a) {
n = a.length;
t = new long[4 * n];
lz = new long[4 * n];
build(a, 1, 0, n - 1);
}
private void build(long[] a, int v, int tl, int tr) {
if (tl == tr) { t[v] = a[tl]; return; }
int tm = (tl + tr) / 2;
build(a, 2 * v, tl, tm);
build(a, 2 * v + 1, tm + 1, tr);
t[v] = t[2 * v] + t[2 * v + 1];
}
private void apply(int v, int tl, int tr, long x) {
t[v] += x * (tr - tl + 1);
lz[v] += x;
}
private void push(int v, int tl, int tr) {
if (lz[v] != 0) {
int tm = (tl + tr) / 2;
apply(2 * v, tl, tm, lz[v]);
apply(2 * v + 1, tm + 1, tr, lz[v]);
lz[v] = 0;
}
}
void add(int l, int r, long x) { add(1, 0, n - 1, l, r, x); }
private void add(int v, int tl, int tr, int l, int r, long x) {
if (r < tl || tr < l) return;
if (l <= tl && tr <= r) { apply(v, tl, tr, x); return; }
push(v, tl, tr);
int tm = (tl + tr) / 2;
add(2 * v, tl, tm, l, r, x);
add(2 * v + 1, tm + 1, tr, l, r, x);
t[v] = t[2 * v] + t[2 * v + 1];
}
long sum(int l, int r) { return sum(1, 0, n - 1, l, r); }
private long sum(int v, int tl, int tr, int l, int r) {
if (r < tl || tr < l) return 0;
if (l <= tl && tr <= r) return t[v];
push(v, tl, tr);
int tm = (tl + tr) / 2;
return sum(2 * v, tl, tm, l, r) + sum(2 * v + 1, tm + 1, tr, l, r);
}
static long seed = 7;
static long next() {
seed = seed * 48271 % 2147483647L;
return seed;
}
private static void check(boolean cond, String msg) {
if (!cond) throw new AssertionError(msg);
}
public static void main(String[] args) {
LazySegTree st = new LazySegTree(new long[] {5, 3, 7, 9, 6, 4, 1, 2});
st.add(1, 5, 2);
check(st.sum(0, 7) == 47 && st.sum(0, 3) == 30 && st.sum(3, 4) == 19, "trace");
int n = 37;
long[] brute = new long[n];
for (int i = 0; i < n; i++) brute[i] = next() % 100;
st = new LazySegTree(brute.clone());
for (int it = 0; it < 2000; it++) {
long op = next() % 2;
int l = (int) (next() % n), r = (int) (next() % n);
if (l > r) { int tmp = l; l = r; r = tmp; }
if (op == 0) {
long x = next() % 50;
st.add(l, r, x);
for (int i = l; i <= r; i++) brute[i] += x;
} else {
long expect = 0;
for (int i = l; i <= r; i++) expect += brute[i];
check(st.sum(l, r) == expect, "random");
}
}
System.out.println("lazy segment tree ok");
}
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>
class LazySegTree {
int n;
std::vector<long long> t, lz;
void build(const std::vector<long long>& a, int v, int tl, int tr) {
if (tl == tr) { t[v] = a[tl]; return; }
int tm = (tl + tr) / 2;
build(a, 2 * v, tl, tm);
build(a, 2 * v + 1, tm + 1, tr);
t[v] = t[2 * v] + t[2 * v + 1];
}
void apply(int v, int tl, int tr, long long x) {
t[v] += x * (tr - tl + 1);
lz[v] += x;
}
void push(int v, int tl, int tr) {
if (lz[v] != 0) {
int tm = (tl + tr) / 2;
apply(2 * v, tl, tm, lz[v]);
apply(2 * v + 1, tm + 1, tr, lz[v]);
lz[v] = 0;
}
}
void add(int v, int tl, int tr, int l, int r, long long x) {
if (r < tl || tr < l) return;
if (l <= tl && tr <= r) { apply(v, tl, tr, x); return; }
push(v, tl, tr);
int tm = (tl + tr) / 2;
add(2 * v, tl, tm, l, r, x);
add(2 * v + 1, tm + 1, tr, l, r, x);
t[v] = t[2 * v] + t[2 * v + 1];
}
long long sum(int v, int tl, int tr, int l, int r) {
if (r < tl || tr < l) return 0;
if (l <= tl && tr <= r) return t[v];
push(v, tl, tr);
int tm = (tl + tr) / 2;
return sum(2 * v, tl, tm, l, r) + sum(2 * v + 1, tm + 1, tr, l, r);
}
public:
explicit LazySegTree(const std::vector<long long>& a)
: n(static_cast<int>(a.size())), t(4 * a.size()), lz(4 * a.size()) {
build(a, 1, 0, n - 1);
}
void add(int l, int r, long long x) { add(1, 0, n - 1, l, r, x); }
long long sum(int l, int r) { return sum(1, 0, n - 1, l, r); }
};
std::int64_t seed = 7;
std::int64_t next() {
seed = seed * 48271 % 2147483647LL;
return seed;
}
int main() {
LazySegTree st({5, 3, 7, 9, 6, 4, 1, 2});
st.add(1, 5, 2);
assert(st.sum(0, 7) == 47 && st.sum(0, 3) == 30 && st.sum(3, 4) == 19);
const int n = 37;
std::vector<long long> brute(n);
for (auto& x : brute) x = next() % 100;
LazySegTree rt(brute);
for (int it = 0; it < 2000; ++it) {
auto op = next() % 2;
int l = static_cast<int>(next() % n), r = static_cast<int>(next() % n);
if (l > r) std::swap(l, r);
if (op == 0) {
long long x = next() % 50;
rt.add(l, r, x);
for (int i = l; i <= r; ++i) brute[i] += x;
} else {
long long expect = 0;
for (int i = l; i <= r; ++i) expect += brute[i];
assert(rt.sum(l, r) == expect);
}
}
std::cout << "lazy segment tree ok\n";
return 0;
}
class LazySegTree {
private n: number;
private t: number[];
private lz: number[];
constructor(a: number[]) {
this.n = a.length;
this.t = new Array<number>(4 * this.n).fill(0);
this.lz = new Array<number>(4 * this.n).fill(0);
this.build(a, 1, 0, this.n - 1);
}
private build(a: number[], v: number, tl: number, tr: number): void {
if (tl === tr) {
this.t[v] = a[tl];
return;
}
const tm = (tl + tr) >> 1;
this.build(a, 2 * v, tl, tm);
this.build(a, 2 * v + 1, tm + 1, tr);
this.t[v] = this.t[2 * v] + this.t[2 * v + 1];
}
private apply(v: number, tl: number, tr: number, x: number): void {
this.t[v] += x * (tr - tl + 1);
this.lz[v] += x;
}
private push(v: number, tl: number, tr: number): void {
if (this.lz[v] !== 0) {
const tm = (tl + tr) >> 1;
this.apply(2 * v, tl, tm, this.lz[v]);
this.apply(2 * v + 1, tm + 1, tr, this.lz[v]);
this.lz[v] = 0;
}
}
add(l: number, r: number, x: number, v = 1, tl = 0, tr = this.n - 1): void {
if (r < tl || tr < l) return;
if (l <= tl && tr <= r) {
this.apply(v, tl, tr, x);
return;
}
this.push(v, tl, tr);
const tm = (tl + tr) >> 1;
this.add(l, r, x, 2 * v, tl, tm);
this.add(l, r, x, 2 * v + 1, tm + 1, tr);
this.t[v] = this.t[2 * v] + this.t[2 * v + 1];
}
sum(l: number, r: number, v = 1, tl = 0, tr = this.n - 1): number {
if (r < tl || tr < l) return 0;
if (l <= tl && tr <= r) return this.t[v];
this.push(v, tl, tr);
const tm = (tl + tr) >> 1;
return this.sum(l, r, 2 * v, tl, tm) + this.sum(l, r, 2 * v + 1, tm + 1, tr);
}
}
let seed = 7;
function next(): number {
seed = (seed * 48271) % 2147483647;
return seed;
}
function check(cond: boolean, msg: string): void {
if (!cond) throw new Error(msg);
}
const st = new LazySegTree([5, 3, 7, 9, 6, 4, 1, 2]);
st.add(1, 5, 2);
check(st.sum(0, 7) === 47 && st.sum(0, 3) === 30 && st.sum(3, 4) === 19, "trace");
const n = 37;
const brute: number[] = [];
for (let i = 0; i < n; i++) brute.push(next() % 100);
const rt = new LazySegTree(brute.slice());
for (let it = 0; it < 2000; it++) {
const op = next() % 2;
let l = next() % n;
let r = next() % n;
if (l > r) [l, r] = [r, l];
if (op === 0) {
const x = next() % 50;
rt.add(l, r, x);
for (let i = l; i <= r; i++) brute[i] += x;
} else {
let expect = 0;
for (let i = l; i <= r; i++) expect += brute[i];
check(rt.sum(l, r) === expect, "random");
}
}
console.log("lazy segment tree ok");
Variant: any monoid, and walking down
A generic recursive tree parameterized by op and identity e, used for min, gcd and the maximum-subarray node. Then two descents: first index at or after l with value at least x (on a max tree) and the k-th one (on a count tree).
from math import gcd, inf
class MonoidSegTree:
def __init__(self, a, op, e):
self.n, self.op, self.e = len(a), op, e
self.t = [e] * (4 * self.n)
self._build(a, 1, 0, self.n - 1)
def _build(self, a, v, tl, tr):
if tl == tr:
self.t[v] = a[tl]
return
tm = (tl + tr) // 2
self._build(a, 2 * v, tl, tm)
self._build(a, 2 * v + 1, tm + 1, tr)
self.t[v] = self.op(self.t[2 * v], self.t[2 * v + 1])
def update(self, p, value, v=1, tl=0, tr=None):
tr = self.n - 1 if tr is None else tr
if tl == tr:
self.t[v] = value
return
tm = (tl + tr) // 2
if p <= tm:
self.update(p, value, 2 * v, tl, tm)
else:
self.update(p, value, 2 * v + 1, tm + 1, tr)
self.t[v] = self.op(self.t[2 * v], self.t[2 * v + 1])
def query(self, l, r, v=1, tl=0, tr=None):
tr = self.n - 1 if tr is None else tr
if r < tl or tr < l:
return self.e
if l <= tl and tr <= r:
return self.t[v]
tm = (tl + tr) // 2
return self.op(self.query(l, r, 2 * v, tl, tm), self.query(l, r, 2 * v + 1, tm + 1, tr))
def first_at_least(self, l, x, v=1, tl=0, tr=None):
"""Smallest i >= l with a[i] >= x; requires op = max. Returns -1 if none."""
tr = self.n - 1 if tr is None else tr
if tr < l or self.t[v] < x:
return -1
if tl == tr:
return tl
tm = (tl + tr) // 2
res = self.first_at_least(l, x, 2 * v, tl, tm)
return res if res != -1 else self.first_at_least(l, x, 2 * v + 1, tm + 1, tr)
def kth_one(self, k, v=1, tl=0, tr=None):
"""Index of the k-th (1-based) one in a 0/1 array; requires op = add."""
tr = self.n - 1 if tr is None else tr
if tl == tr:
return tl
tm = (tl + tr) // 2
left = self.t[2 * v]
if k <= left:
return self.kth_one(k, 2 * v, tl, tm)
return self.kth_one(k - left, 2 * v + 1, tm + 1, tr)
a = [5, 3, 7, 9, 6, 4, 1, 2]
mn = MonoidSegTree(a, min, inf)
assert mn.query(2, 6) == 1 and mn.query(0, 3) == 3
g = MonoidSegTree([12, 18, 24, 36, 9], gcd, 0)
assert g.query(0, 3) == 6 and g.query(3, 4) == 9 and g.query(0, 4) == 3
mx = MonoidSegTree(a, max, -inf)
assert mx.first_at_least(0, 8) == 3 and mx.first_at_least(4, 5) == 4
assert mx.first_at_least(5, 5) == -1 and mx.first_at_least(0, 10) == -1
mx.update(6, 11)
assert mx.first_at_least(4, 10) == 6
alive = MonoidSegTree([1] * 8, lambda x, y: x + y, 0)
order = []
for k in [3, 3, 1]: # remove the 3rd, then 3rd, then 1st remaining
i = alive.kth_one(k)
order.append(i)
alive.update(i, 0)
assert order == [2, 3, 0]
print("monoid + descent ok")
Variant: maximum subarray sum in a range
Each node stores (sum, best prefix, best suffix, best). The merge is the whole trick: the best subarray of a concatenation is the best of the left, the best of the right, or a suffix of the left joined to a prefix of the right.
from math import inf
E = (0, -inf, -inf, -inf) # identity: empty segment
def merge(a, b):
s1, p1, x1, b1 = a
s2, p2, x2, b2 = b
return (s1 + s2, max(p1, s1 + p2), max(x2, s2 + x1), max(b1, b2, x1 + p2))
def leaf(v):
return (v, v, v, v)
def build(arr):
n = len(arr)
t = [E] * (4 * n)
def go(v, tl, tr):
if tl == tr:
t[v] = leaf(arr[tl])
return
tm = (tl + tr) // 2
go(2 * v, tl, tm)
go(2 * v + 1, tm + 1, tr)
t[v] = merge(t[2 * v], t[2 * v + 1])
go(1, 0, n - 1)
return t
def query(t, n, l, r, v=1, tl=0, tr=None):
tr = n - 1 if tr is None else tr
if r < tl or tr < l:
return E
if l <= tl and tr <= r:
return t[v]
tm = (tl + tr) // 2
return merge(query(t, n, l, r, 2 * v, tl, tm), query(t, n, l, r, 2 * v + 1, tm + 1, tr))
def brute(arr, l, r):
return max(sum(arr[i:j + 1]) for i in range(l, r + 1) for j in range(i, r + 1))
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
t = build(arr)
assert query(t, len(arr), 0, 8)[3] == 6 # [4, -1, 2, 1]
assert query(t, len(arr), 0, 2)[3] == 1
assert query(t, len(arr), 7, 7)[3] == -5 # non-empty: forced to take -5
for l in range(len(arr)):
for r in range(l, len(arr)):
assert query(t, len(arr), l, r)[3] == brute(arr, l, r)
print("max subarray node ok")
Variant: a non-commutative monoid, iteratively
Composition of linear functions . The query returns "apply , then , …, then ". Order matters, so the bottom-up loop keeps a left and a right accumulator. Tested against brute force on all ranges of a size-7 array.
M = 998244353
ID = (1, 0)
def then(f, g): # apply f first, then g
return (g[0] * f[0] % M, (g[0] * f[1] + g[1]) % M)
class IterativeMonoid:
def __init__(self, items):
self.n = n = len(items)
self.t = [ID] * n + list(items)
for i in range(n - 1, 0, -1):
self.t[i] = then(self.t[2 * i], self.t[2 * i + 1])
def query(self, l, r): # composition over [l, r), in order
resl, resr = ID, ID
l += self.n
r += self.n
while l < r:
if l & 1:
resl = then(resl, self.t[l])
l += 1
if r & 1:
r -= 1
resr = then(self.t[r], resr)
l >>= 1
r >>= 1
return then(resl, resr)
fs = [(2, 3), (5, 1), (1, 7), (3, 0), (4, 4), (6, 2), (1, 1)]
tree = IterativeMonoid(fs)
for l in range(len(fs)):
for r in range(l + 1, len(fs) + 1):
acc = ID
for f in fs[l:r]:
acc = then(acc, f)
assert tree.query(l, r) == acc
assert tree.query(0, 2) == (10, 16) # x -> 2x+3 -> 5(2x+3)+1 = 10x+16
print("non-commutative iterative ok")
Variant: range assign + range add + range sum
The tag is (assign or None, add) with the composition rule derived above.
class AssignAddTree:
def __init__(self, a):
self.n = len(a)
self.t = [0] * (4 * self.n)
self.st = [None] * (4 * self.n) # pending assign
self.ad = [0] * (4 * self.n) # pending add (applied after the assign)
self._build(a, 1, 0, self.n - 1)
def _build(self, a, v, tl, tr):
if tl == tr:
self.t[v] = a[tl]
return
tm = (tl + tr) // 2
self._build(a, 2 * v, tl, tm)
self._build(a, 2 * v + 1, tm + 1, tr)
self.t[v] = self.t[2 * v] + self.t[2 * v + 1]
def _apply(self, v, length, s, d):
if s is not None: # assign wipes the old tag
self.t[v] = s * length
self.st[v], self.ad[v] = s, 0
if d:
self.t[v] += d * length
self.ad[v] += d
def _push(self, v, tl, tr):
if self.st[v] is not None or self.ad[v]:
tm = (tl + tr) // 2
self._apply(2 * v, tm - tl + 1, self.st[v], self.ad[v])
self._apply(2 * v + 1, tr - tm, self.st[v], self.ad[v])
self.st[v], self.ad[v] = None, 0
def update(self, l, r, s, d, v=1, tl=0, tr=None):
tr = self.n - 1 if tr is None else tr
if r < tl or tr < l:
return
if l <= tl and tr <= r:
self._apply(v, tr - tl + 1, s, d)
return
self._push(v, tl, tr)
tm = (tl + tr) // 2
self.update(l, r, s, d, 2 * v, tl, tm)
self.update(l, r, s, d, 2 * v + 1, tm + 1, tr)
self.t[v] = self.t[2 * v] + self.t[2 * v + 1]
def sum(self, l, r, v=1, tl=0, tr=None):
tr = self.n - 1 if tr is None else tr
if r < tl or tr < l:
return 0
if l <= tl and tr <= r:
return self.t[v]
self._push(v, tl, tr)
tm = (tl + tr) // 2
return self.sum(l, r, 2 * v, tl, tm) + self.sum(l, r, 2 * v + 1, tm + 1, tr)
seed, n = 2024, 23
def rnd():
global seed
seed = seed * 48271 % 2147483647
return seed
brute = [rnd() % 10 for _ in range(n)]
tree = AssignAddTree(brute)
for _ in range(3000):
op, l, r = rnd() % 3, rnd() % n, rnd() % n
l, r = min(l, r), max(l, r)
if op == 0:
x = rnd() % 10
tree.update(l, r, x, 0)
brute[l:r + 1] = [x] * (r - l + 1)
elif op == 1:
x = rnd() % 10
tree.update(l, r, None, x)
for i in range(l, r + 1):
brute[i] += x
else:
assert tree.sum(l, r) == sum(brute[l:r + 1])
print("assign + add ok")
Variant: persistent segment tree, k-th smallest in a range
class PersistentKth:
def __init__(self, a):
self.vals = sorted(set(a))
rank = {v: i for i, v in enumerate(self.vals)}
self.m = len(self.vals)
self.L, self.R, self.cnt = [0], [0], [0] # node 0: the empty tree, points to itself
self.roots = [0]
for x in a:
self.roots.append(self._insert(self.roots[-1], 0, self.m - 1, rank[x]))
def _new(self, left, right, c):
self.L.append(left)
self.R.append(right)
self.cnt.append(c)
return len(self.cnt) - 1
def _insert(self, prev, lo, hi, pos): # path copying: new nodes only on one path
if lo == hi:
return self._new(0, 0, self.cnt[prev] + 1)
mid = (lo + hi) // 2
if pos <= mid:
return self._new(self._insert(self.L[prev], lo, mid, pos), self.R[prev], self.cnt[prev] + 1)
return self._new(self.L[prev], self._insert(self.R[prev], mid + 1, hi, pos), self.cnt[prev] + 1)
def kth(self, l, r, k): # k-th smallest (1-based) in a[l..r]
u, v = self.roots[l], self.roots[r + 1]
lo, hi = 0, self.m - 1
while lo < hi:
mid = (lo + hi) // 2
left = self.cnt[self.L[v]] - self.cnt[self.L[u]]
if k <= left:
u, v, hi = self.L[u], self.L[v], mid
else:
k -= left
u, v, lo = self.R[u], self.R[v], mid + 1
return self.vals[lo]
a = [5, 3, 7, 9, 6, 4, 1, 2]
pk = PersistentKth(a)
assert [pk.kth(2, 6, k) for k in range(1, 6)] == [1, 4, 6, 7, 9]
assert len(pk.cnt) == 1 + 8 * 4 # 8 inserts x (log2(8) + 1) new nodes each
b = [(i * 37) % 11 for i in range(30)]
pb = PersistentKth(b)
for l in range(0, 30, 3):
for r in range(l, 30, 4):
s = sorted(b[l:r + 1])
assert all(pb.kth(l, r, k + 1) == s[k] for k in range(len(s)))
print("persistent kth ok")
Variant: segment tree beats (range chmin, range sum, range max)
NEG = float("-inf")
class Beats:
def __init__(self, a):
self.n = n = len(a)
self.mx = [0] * (4 * n)
self.se = [NEG] * (4 * n) # strict second maximum
self.mc = [0] * (4 * n) # count of the maximum
self.sm = [0] * (4 * n)
self._build(a, 1, 0, n - 1)
def _pull(self, v):
l, r = 2 * v, 2 * v + 1
mx, se, mc = self.mx, self.se, self.mc
self.sm[v] = self.sm[l] + self.sm[r]
if mx[l] == mx[r]:
mx[v], mc[v], se[v] = mx[l], mc[l] + mc[r], max(se[l], se[r])
elif mx[l] > mx[r]:
mx[v], mc[v], se[v] = mx[l], mc[l], max(se[l], mx[r])
else:
mx[v], mc[v], se[v] = mx[r], mc[r], max(mx[l], se[r])
def _build(self, a, v, tl, tr):
if tl == tr:
self.mx[v], self.mc[v], self.sm[v] = a[tl], 1, a[tl]
return
tm = (tl + tr) // 2
self._build(a, 2 * v, tl, tm)
self._build(a, 2 * v + 1, tm + 1, tr)
self._pull(v)
def _tag(self, v, x): # valid when se[v] < x: only the maxima change
if x < self.mx[v]:
self.sm[v] -= (self.mx[v] - x) * self.mc[v]
self.mx[v] = x
def _push(self, v):
self._tag(2 * v, self.mx[v])
self._tag(2 * v + 1, self.mx[v])
def chmin(self, l, r, x, v=1, tl=0, tr=None):
tr = self.n - 1 if tr is None else tr
if r < tl or tr < l or self.mx[v] <= x:
return # case 1: nothing changes
if l <= tl and tr <= r and self.se[v] < x:
self._tag(v, x) # case 2: only the maxima change
return
self._push(v) # case 3: break the node
tm = (tl + tr) // 2
self.chmin(l, r, x, 2 * v, tl, tm)
self.chmin(l, r, x, 2 * v + 1, tm + 1, tr)
self._pull(v)
def query(self, l, r, v=1, tl=0, tr=None): # returns (sum, max)
tr = self.n - 1 if tr is None else tr
if r < tl or tr < l:
return 0, NEG
if l <= tl and tr <= r:
return self.sm[v], self.mx[v]
self._push(v)
tm = (tl + tr) // 2
s1, m1 = self.query(l, r, 2 * v, tl, tm)
s2, m2 = self.query(l, r, 2 * v + 1, tm + 1, tr)
return s1 + s2, max(m1, m2)
seed, n = 99, 41
def rnd():
global seed
seed = seed * 48271 % 2147483647
return seed
brute = [rnd() % 1000 for _ in range(n)]
bt = Beats(brute)
for _ in range(3000):
op, l, r = rnd() % 2, rnd() % n, rnd() % n
l, r = min(l, r), max(l, r)
if op == 0:
x = rnd() % 1000
bt.chmin(l, r, x)
for i in range(l, r + 1):
brute[i] = min(brute[i], x)
else:
assert bt.query(l, r) == (sum(brute[l:r + 1]), max(brute[l:r + 1]))
print("segment tree beats ok")
Variant: dynamic (sparse) segment tree over
class DynamicSegTree:
def __init__(self, lo, hi):
self.lo, self.hi = lo, hi
self.left, self.right, self.total = [0, 0], [0, 0], [0, 0] # 0 = null, 1 = root
def _new(self):
self.left.append(0)
self.right.append(0)
self.total.append(0)
return len(self.total) - 1
def add(self, pos, delta):
v, lo, hi = 1, self.lo, self.hi
while True:
self.total[v] += delta
if lo == hi:
return
mid = (lo + hi) // 2
if pos <= mid:
if not self.left[v]:
self.left[v] = self._new()
v, hi = self.left[v], mid
else:
if not self.right[v]:
self.right[v] = self._new()
v, lo = self.right[v], mid + 1
def query(self, l, r, v=1, lo=None, hi=None):
lo = self.lo if lo is None else lo
hi = self.hi if hi is None else hi
if v == 0 or r < lo or hi < l:
return 0
if l <= lo and hi <= r:
return self.total[v]
mid = (lo + hi) // 2
return self.query(l, r, self.left[v], lo, mid) + self.query(l, r, self.right[v], mid + 1, hi)
d = DynamicSegTree(0, 10**9)
d.add(10**9, 5)
d.add(0, 3)
d.add(123456789, 7)
assert d.query(0, 10**9) == 15 and d.query(1, 10**9 - 1) == 7 and d.query(10**9, 10**9) == 5
assert len(d.total) - 1 <= 1 + 3 * 30 # at most ceil(log2(1e9 + 1)) = 30 new nodes per insert
print("dynamic segment tree ok")
Real-world uses
Segment trees are, honestly, more common in contests and interviews than in production code — production systems often get the same effect from B-trees with subtree aggregates, from pre-aggregated rollups, or from Fenwick trees. But the structure and its ideas do run in real systems:
- Prioritized experience replay in reinforcement learning. Schaul et al. ("Prioritized Experience Replay", ICLR 2016) sample transitions with probability proportional to priority using a sum tree: a segment tree over priorities, sampled by drawing and walking down by prefix sums. OpenAI Baselines ships
baselines/common/segment_tree.pywithSumSegmentTreeandMinSegmentTreefor exactly this, and most RL libraries have an equivalent. - Computational geometry and VLSI. Bentley's original application: the area (or perimeter) of a union of axis-aligned rectangles by a sweep line, with a segment tree over y-coordinates storing cover counts. Union-area and overlap computations of this kind appear in chip layout verification and GIS. See spatial indexing.
- Allocators and schedulers that search for free space. "Find the first free block of at least units" is a walk down a tree that stores the largest free run per subtree. Several buddy-allocator implementations store the largest free block size per subtree in a binary tree and descend it in exactly this way. See memory allocators.
- Weighted random selection and load balancing. Picking a server with probability proportional to a changing weight is a prefix-sum descent with point updates — a sum tree (or Fenwick tree) instead of rebuilding a cumulative array on every weight change. See load balancing algorithms.
- Aggregate trees in databases and time-series stores. The disk-friendly cousin is a B-tree whose internal nodes store counts or sums of their subtrees (order-statistic or "counted" B-trees), so
COUNTover a key range or "the k-th row" costs . Time-series databases precompute multi-resolution rollups (per-minute, per-hour, per-day aggregates) — a dyadic decomposition of time with a fixed fan-out. See time-series databases and query planning. - Persistent structures in functional languages and version stores. Path copying, which persistent segment trees use, is how immutable maps and vectors (Clojure, Scala, Haskell's containers) share structure between versions, and how copy-on-write B-trees (LMDB, Btrfs) produce snapshots.
- GPU reductions and graphics. Parallel reduction and scan build exactly this tree of partial aggregates level by level; mipmap pyramids are a 2D bottom-up aggregation of the same shape.
Pitfalls & edge cases
- Array too small. The recursive layout needs , not ; fails for (index 9 is used). The iterative layout needs exactly .
- Inclusive versus half-open bounds. The recursive code here uses , the iterative code . Mixing them is the most common off-by-one. Pick one per codebase and convert at the API boundary.
- Wrong identity. Min needs (not 0), max needs , gcd needs 0, product needs 1, matrices need the identity matrix. A sum tree with identity 0 used for min silently returns 0.
- Forgetting to push in queries. Pushing only in updates leaves stale children; queries that descend below a tagged node read wrong values. Push before every descent.
- Forgetting to pull after updates. After recursing into children, recompute the node.
- Tag scaling by length. For range add with sums, the node changes by , not . For range add with min/max, by alone. Getting this wrong passes tests on length-1 segments.
- Composition order. Range assign followed by add is different from add followed by assign. The tag must encode order; write down the composition rule before coding.
- Overflow. Sums of values up to need 64-bit integers; lazy
x * lengthcan overflow 32-bit even when values are small. - Non-commutative merges in the iterative query. A single accumulator reverses the right-hand part. Use
reslandresr. - Recursion depth. Depth is only , so the recursive tree is safe; but Python's per-call overhead makes recursive trees slow for — prefer the iterative form or arrays of primitives.
- Empty array.
n = 0breaks the recursive build (tr = -1). Guard it. - Persistent memory. Each update adds nodes; updates on is about nodes. Preallocate arrays; do not use objects per node in Java or Python.
- Lazy with persistence. Pushing a tag modifies children that older versions share. Either copy children on push or use "tag stays on the node" (non-propagating) designs.
Variations
- Fenwick tree (BIT): prefix aggregates with cells, invertible operations only. Fenwick trees.
- Sparse table: static, idempotent operations, query, memory. Sqrt decomposition and Mo's algorithm for operations with no good merge. Sparse tables, sqrt decomposition & Mo's algorithm.
- Merge-sort tree: each node stores the sorted list of its segment; "how many in are " in , static. With fractional cascading, .
- Li Chao tree: a segment tree over x-coordinates where each node keeps one line; inserts lines and answers "min over lines at x" in . Used for convex hull trick optimizations in DP.
- Segment tree on a tree: flatten with an Euler tour so subtrees become ranges (LCA, binary lifting & Euler tour), or decompose paths into chains (heavy-light decomposition).
- Segment tree over time / offline divide and conquer: each operation lives on an interval of time; insert it into nodes and DFS with rollbacks (dynamic connectivity offline with a rollback union-find).
- Kinetic segment trees, wavelet trees: wavelet trees answer k-th smallest and rank queries in with succinct memory — an alternative to persistent segment trees for static arrays.
- Interval tree and the "original" segment tree: storing intervals for stabbing queries, covered in spatial trees.
Practice ladder
Each problem is described in my own words; follow the link for the formal statement.
1. Range Sum Query – Mutable (LeetCode 307) — Point assignment and range sums. The iterative tree above, verbatim.
Hint
Store leaves at t[n + i]. Update walks up with p >>= 1; query uses the half-open loop.
2. Dynamic Range Sum Queries (CSES 1648) — The same at with values up to . Teaches 64-bit sums and fast I/O.
Hint
Use long long / long. In Python, read all input at once and use the iterative tree with a flat list; recursion will be too slow.
3. Dynamic Range Minimum Queries (CSES 1649) — Point updates, range minimum. Teaches swapping the monoid (identity ).
Hint
Replace + with min and the identity 0 with a large value. Everything else is unchanged.
4. Range Update Queries (CSES 1651) — Add to a range, read one element. Teaches that range-update/point-query needs no lazy tags at all.
Hint
Either keep a difference array in a point-update/prefix-sum tree, or store adds on the canonical nodes of the range and answer a point query by summing the tags on the leaf-to-root path.
5. Hotel Queries (CSES 1143) — Groups arrive in order; each takes the first hotel with enough free rooms. Teaches walking down a max tree.
Hint
Max tree over free rooms. For each group, descend to the leftmost leaf with value group size, print it, subtract, update. One descent per group.
Solution
def hotel_queries(rooms: list[int], groups: list[int]) -> list[int]:
n = len(rooms)
size = 1
while size < n:
size *= 2
t = [0] * (2 * size) # perfect tree, padding leaves hold 0
t[size:size + n] = rooms
for i in range(size - 1, 0, -1):
t[i] = max(t[2 * i], t[2 * i + 1])
out = []
for g in groups:
if t[1] < g:
out.append(0)
continue
v = 1
while v < size: # go left whenever the left child suffices
v = 2 * v if t[2 * v] >= g else 2 * v + 1
out.append(v - size + 1) # 1-based hotel number
t[v] -= g
v //= 2
while v:
t[v] = max(t[2 * v], t[2 * v + 1])
v //= 2
return out
assert hotel_queries([3, 2, 4, 1, 5, 5, 2, 6], [4, 4, 7, 1, 1]) == [3, 5, 0, 1, 1]
print("1143 ok")
. Padding to a power of two makes the descent a simple loop.
6. List Removals (CSES 1749) — Repeatedly remove and print the element at a given position of the current list. Teaches the k-th-one descent on a count tree.
Hint
Count tree over "still present" flags. Position in the current list is the -th one; descend, print, set to 0.
7. Xenia and Bit Operations (Codeforces 339D) — A complete binary tree alternately ORs and XORs pairs upward; after each point update print the root. Teaches that the merge can depend on the level.
Hint
Store the level parity with each node (or compute it from depth). Leaves' parents use OR, the next level XOR, alternating. Only the path to the root changes on an update.
8. Subarray Sum Queries (CSES 1190) — Point updates; after each, report the maximum subarray sum of the whole array (empty allowed). Teaches the four-field node merge.
Hint
Use the (sum, prefix, suffix, best) node from the variant above, but clamp at 0 since the empty subarray is allowed: leaves become (v, max(v,0), max(v,0), max(v,0)).
9. Range Updates and Sums (CSES 1735) — Range add, range assign, range sum. Teaches tag composition. The AssignAddTree variant above is the solution.
Hint
The tag is "assign (optional), then add". A new assign replaces the whole tag; a new add accumulates. Apply in that order.
10. Prefix Sum Queries (CSES 2166) — Point updates; query the maximum prefix sum of a subarray. Teaches a two-field node (sum, best prefix).
Hint
Merge: sum = s1 + s2, pref = max(p1, s1 + p2). Whether the empty prefix counts (value 0) is in the statement; handle it at the end.
11. Booking Concert Tickets in Groups (LeetCode 2286) — Book k consecutive seats in one row, or k seats scattered over rows, up to a row limit. Teaches combining a max-tree descent with a sum tree.
Hint
Keep the free seats per row in a max tree (for "first row with ≥ k free") and a sum tree (for "enough seats in rows 0..maxRow"). For scattered booking, fill rows from the first non-full row onward and remember that pointer.
12. Falling Squares (LeetCode 699) — Squares drop onto a line and stack; report the tallest stack after each drop. Teaches range-max query + range-assign update with coordinate compression.
Hint
Compress all left and right edges. For each square: h = max over its span + side, then assign h over the span. Lazy assign with max aggregation.
13. K-th Number (SPOJ MKTHNUM) — Static array, many queries for the k-th smallest in a subarray. Teaches the persistent segment tree — the PersistentKth variant above.
Hint
Version counts the first elements over compressed values. Descend versions and together using count differences.
14. Range Queries and Copies (CSES 1737) — Point assignments and range sums on several arrays, plus "copy array k into a new array". Teaches persistence for O(1)-cost copies.
Hint
A copy is just a new root pointer to the same tree. Updates path-copy, so the original is unaffected.
Solution
def range_queries_and_copies(a: list[int], ops: list[tuple]) -> list[int]:
n = len(a)
L, R, S = [0], [0], [0]
def new(l, r, s):
L.append(l); R.append(r); S.append(s)
return len(S) - 1
def build(lo, hi):
if lo == hi:
return new(0, 0, a[lo])
mid = (lo + hi) // 2
lc, rc = build(lo, mid), build(mid + 1, hi)
return new(lc, rc, S[lc] + S[rc])
def assign(v, lo, hi, p, x): # returns the new root of the copied path
if lo == hi:
return new(0, 0, x)
mid = (lo + hi) // 2
if p <= mid:
lc, rc = assign(L[v], lo, mid, p, x), R[v]
else:
lc, rc = L[v], assign(R[v], mid + 1, hi, p, x)
return new(lc, rc, S[lc] + S[rc])
def query(v, lo, hi, l, r):
if r < lo or hi < l:
return 0
if l <= lo and hi <= r:
return S[v]
mid = (lo + hi) // 2
return query(L[v], lo, mid, l, r) + query(R[v], mid + 1, hi, l, r)
roots, out = [build(0, n - 1)], []
for op in ops: # 1-based array ids and positions, as in the task
if op[0] == 1:
_, k, p, x = op
roots[k - 1] = assign(roots[k - 1], 0, n - 1, p - 1, x)
elif op[0] == 2:
_, k, l, r = op
out.append(query(roots[k - 1], 0, n - 1, l - 1, r - 1))
else:
roots.append(roots[op[1] - 1]) # O(1) copy: share the whole tree
return out
ops = [(2, 1, 2, 3), (3, 1), (1, 2, 1, 5), (2, 2, 1, 2), (2, 1, 1, 2), (1, 1, 2, 10), (2, 2, 2, 3)]
assert range_queries_and_copies([2, 3, 1, 2, 5], ops) == [4, 8, 5, 4]
print("1737 ok")
per update or query, new nodes per update, per copy.
15. Gorgeous Sequence (HDU 5306) — Range chmin, range max, range sum. The canonical segment-tree-beats problem; the Beats variant above implements it.
Hint
Store max, strict second max, count of max and sum. Stop when max ≤ x; tag when second max < x; otherwise recurse. The amortized bound is .
For a structured path through all of this, the Codeforces EDU section has a free segment tree course with graded problem sets, and CSES's "Range Queries" section is the standard drill set.
Common mistakes & interview follow-ups
"Why not prefix sums?" Updates. Prefix sums cost per update; with interleaved operations you need for both.
"Why not a Fenwick tree?" For sums with point updates, a Fenwick tree is shorter and faster — say so. A segment tree is needed for non-invertible operations (min, max, gcd), custom merges (max subarray), range assignment, descents with arbitrary predicates, and persistence.
"How much memory?" for the recursive layout, iterative, double that with lazy tags. Explain the bound in one sentence: the tree's height is and heap indices at that depth stay below .
"What if indices go up to ?" Compress if the operations are known in advance; otherwise use a dynamic tree that allocates nodes on demand, memory.
"What if queries are on old versions?" Persistent segment tree via path copying, extra nodes per update.
"Can you do range chmin?" Not with a plain lazy tag; segment tree beats with (max, second max, count) gives amortized .
"Can it be parallel or concurrent?" Batch updates can be applied bottom-up level by level in parallel. Concurrent single updates contend on the root; real systems usually shard, or batch and rebuild.
"Explain lazy propagation in one minute." Put the update on the covering nodes, update their values, remember the rest as a tag, and push tags down only when an operation needs to pass through. Name apply, push and pull, and the invariant.
Common mistakes interviewers watch for: size for a recursive tree; wrong identity for min; not pushing in queries; x instead of x * length; mixing inclusive and exclusive bounds; 32-bit overflow on sums.
Quick quiz
1. For a = [5, 3, 7, 9, 6, 4, 1, 2], which nodes form the canonical decomposition of ?
Answer
[1], [2,3], [4,5], [6] — sums 3, 16, 10, 1, total 30. The root, [0,3], [0,1], [4,7] and [6,7] are partial; [0] and [7] are disjoint.
2. Why does a range query visit at most 4 nodes per level?
Answer
Only partial nodes recurse. A partial node must contain the left boundary pair or the right pair , and at one level at most one node contains each pair, so at most 2 nodes recurse, producing at most 4 visits at the next level.
3. What breaks if you push tags only during updates and not during queries?
Answer
A query that descends below a tagged node reads children that have not received the tag, so it returns stale values. The parent's value is correct; its children's are not until pushed.
4. In a range-assign + range-add tree, a node has tag (assign 4, add 3). A new "add 2" arrives, then "assign 1". What is the tag after each?
Answer
After add 2: (assign 4, add 5). After assign 1: (assign 1, add 0) — the assign wipes everything before it.
5. How many new nodes does one update create in a persistent segment tree over positions?
Answer
One per level of the root-to-leaf path: .
Further reading / sources
- Al.Cash, "Efficient and easy segment trees", Codeforces blog entry 18051 (2015) — the bottom-up layout, non-commutative queries and lazy propagation without recursion.
- cp-algorithms: Segment Tree — recursive implementation, descents, persistent trees, 2D trees, and many merges.
- jiry_2 (Ji Ruyi), "A simple introduction to 'Segment tree beats'", Codeforces blog entry 57319 (2018), summarizing the 2016 Chinese IOI team paper.
- J. R. Driscoll, N. Sarnak, D. D. Sleator, R. E. Tarjan, "Making Data Structures Persistent", Journal of Computer and System Sciences 38(1), 1989.
- Jon L. Bentley, "Solutions to Klee's rectangle problems", unpublished notes, Carnegie Mellon University, 1977; Mark de Berg et al., Computational Geometry: Algorithms and Applications, 3rd ed., chapter 10 "More Geometric Data Structures" (interval and segment trees in the geometric sense).
- Antti Laaksonen, Competitive Programmer's Handbook, chapter 9 "Range queries" and chapter 28 "Segment trees revisited" (lazy propagation, dynamic and persistent trees).
- Tom Schaul, John Quan, Ioannis Antonoglou, David Silver, "Prioritized Experience Replay", ICLR 2016 (the sum-tree sampler).
- Michael Fredman and Michael Saks, "The cell probe complexity of dynamic data structures", STOC 1989; Mihai Pătrașcu and Erik Demaine, "Tight bounds for the partial-sums problem", SODA 2004.
Previous lesson: Tries in Depth · Next lesson: Fenwick Trees (Binary Indexed Trees)
Related: Module 3 overview · Trees overview · Advanced Data Structures · Prefix Sums & Difference Arrays · Heaps & Priority Queues · Sparse Tables & Sqrt Decomposition · Capstone: A Range-Query Engine · Recursion & Induction · Course home