Chapter 8 · Data Structures on Trees
Segment Tree
One combining function, three shapes (plain, lazy, persistent), and the invariant that makes every variant obvious.
Store, for every node v covering a range [l,r), the aggregate of that range. Combine children on the way up, and on a query keep two accumulators (left result, right result) while descending — the result is not commutative-safe unless you say so.
struct Seg { // n = power of two, [l, r)
int n; vector<ll> t;
Seg(int m) { n = 1; while (n < m) n *= 2; t.assign(2 * n, 0); }
void build(const vector<ll>& a) {
for (int i = 0; i < (int)a.size(); i++) t[n + i] = a[i];
for (int i = n - 1; i > 0; i--) t[i] = t[2*i] + t[2*i+1];
}
void setv(int p, ll x) { for (t[p += n] = x; p > 1; p >>= 1) t[p>>1] = t[2*p] + t[2*p+1]; }
ll query(int l, int r) { // half-open
ll s = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) s += t[l++];
if (r & 1) s += t[--r];
}
return s;
}
};4n (or 2·pow2), and why the iterative version is 2nThe recursive layout needs up to 4n nodes because ranges split unevenly; the bottom-up layout packs a complete tree of pow2 leaves into 2n cells with no gaps. The iterative version is faster (no recursion, no function calls), needs no build recursion and no push logic — and it cannot do lazy propagation, which is the only reason to prefer the recursive one.
Everything is the same code with a different combine
combine | query | extra needed |
|---|---|---|
+ | range sum | lazy for range add |
min / max | range min/max | lazy for range add (shift both) |
| gcd | range gcd | gcd(al, suffix differences) — the standard trick |
| count of ones | "first position with value ≥ x" | descend by comparing t[2v] |
| matrix | linear recurrences | Linear Recurrences from Graphs and Matrices |
or of bitsets | reachability | O(n2/64) memory, careful |
#Lazy propagation, without the folklore
t[v] is always the correct answer for v's range as if all pending updates on the path to v were applied; lazy[v] is what still has to be pushed to v's children.
struct Lazy {
int n; vector<ll> t, lz;
Lazy(int m) { n = 1; while (n < m) n *= 2; t.assign(2*n, 0); lz.assign(2*n, 0); }
void apply(int v, int l, int r, ll x) { t[v] += x * (r - l); if (r - l > 1) lz[v] += x; }
void push(int v, int l, int r) {
if (!lz[v]) return;
int m = (l + r) >> 1;
apply(2*v, l, m, lz[v]); apply(2*v+1, m, r, lz[v]);
lz[v] = 0;
}
void upd(int v, int l, int r, int ql, int qr, ll x) {
if (r <= ql || qr <= l) return;
if (ql <= l && r <= qr) return apply(v, l, r, x), void();
push(v, l, r);
int m = (l + r) >> 1;
upd(2*v, l, m, ql, qr, x); upd(2*v+1, m, r, ql, qr, x);
t[v] = t[2*v] + t[2*v+1];
}
ll ask(int v, int l, int r, int ql, int qr) {
if (r <= ql || qr <= l) return 0;
if (ql <= l && r <= qr) return t[v];
push(v, l, r);
int m = (l + r) >> 1;
return ask(2*v, l, m, ql, qr) + ask(2*v+1, m, r, ql, qr);
}
};- Forgetting
pushbefore descending in bothupdandask— the children then answer with stale values while the parent looks right. - Applying the update to
t[v]without multiplying by the length (sum) or by the count of affected elements (chmax/chmin need the "second maximum" trick, not a length). - Using one lazy value for two different operations (add and assign): assign must override, so
lzneeds a tag type plus a "set" flag, and the ordering is set-then-add, never the reverse.
For "range chmin + range sum/max", store max and second-max per node; a chmin(x) with second-max < x ≤ max only touches the top value, so you can update it in O(1) and push lazily — amortised O(log2 n) per operation. The general lesson: store enough auxiliary information that the update becomes trivial at the node, and prove the amortised bound with a potential (here: how many times a value can be reduced).
Three more segment-tree shapes worth owning
- merge-sort tree: each node keeps its sorted array — "count values in [l,r) within [x,y]" in O(log2 n), static and simple,
- persistent: path-copy O(log n) nodes per update; "k-th smallest in a subarray" and all "offline prefix" queries in O(log n) with O(nlog n) memory,
- implicit / dynamic: build nodes on demand over a range up to 109 — "add interval, query max" with coordinates too large to compress because updates are online.
Query ranges marked on the tree: exactly the nodes that get taken, at most two per level, which is the O(log n) proof in one picture.