vi. Dynamic and Persistent Segment Trees

Dynamic (implicit) segment trees create nodes only when an update touches them, so the coordinate range can be $10^{18}$ with $O(q\log C)$ memory. Persistent trees copy the touched path so every version survives. Both use index-based nodes, and both pair naturally with tag permanence (tags never pushed down).

Dynamic segment tree (range add, range sum)

struct DynSeg {
    ll lo, hi; vector<array<int, 2>> ch{{0, 0}}; vector<ll> sum{0}, tag{0};   // node 0 = root
    DynSeg(ll lo, ll hi) : lo(lo), hi(hi) {}
    int child(int p, int c) {
        if (!ch[p][c]) { ch[p][c] = sz(ch); ch.push_back({0, 0}); sum.push_back(0); tag.push_back(0); }
        return ch[p][c];
    }
    void add(int p, ll l, ll r, ll x, ll y, ll v) {    // [x, y) within node [l, r)
        x = max(x, l); y = min(y, r); if (x >= y) return;
        sum[p] += v * (y - x);
        if (x == l && y == r) { tag[p] += v; return; }
        ll m = l + (r - l) / 2;
        if (x < m) { int c = child(p, 0); add(c, l, m, x, y, v); }
        if (m < y) { int c = child(p, 1); add(c, m, r, x, y, v); }
    }
    ll query(int p, ll l, ll r, ll x, ll y) const {
        x = max(x, l); y = min(y, r); if (x >= y) return 0;
        if (x == l && y == r) return sum[p];
        ll m = l + (r - l) / 2, res = tag[p] * (y - x);
        if (ch[p][0]) res += query(ch[p][0], l, m, x, y);
        if (ch[p][1]) res += query(ch[p][1], m, r, x, y);
        return res;
    }
    void add(ll x, ll y, ll v) { add(0, lo, hi, x, y, v); }
    ll query(ll x, ll y) const { return query(0, lo, hi, x, y); }
};

Proof: dynamic segment tree correctness and node count

Correctness. This is the ordinary recursive segment tree with tag permanence (sum-with-coverage-tag, no push-down), restricted to only ever materializing a child when add or query actually needs to recurse into it. add(p,l,r,x,y,v) updates sum[p] by $v\times (\text{overlap length})$ unconditionally (correct regardless of whether the node is fully, partially, or not covered — the clamping x=max(x,l); y=min(y,r) makes the overlap length right in all three cases, and $0$ when disjoint) and additionally stores a permanent tag[p] += v exactly when $[x,y)$ fully covers $[l,r)$ — never pushed down, never cleared. query(p,l,r,x,y) returns tag[p]*(overlap) (every pending full-coverage add on $p$ itself, correctly scaled) plus the recursive contribution of whichever children exist; a non-existent child is equivalent to an all-zero subtree with no tags, contributing $0$, which is exactly what skipping it computes. By induction on tree depth, sum[p] always equals the true total over $[l,r)$ (it’s updated by every add that touches any part of $[l,r)$, scaled by the exact overlap, matching the ordinary eager segment tree), and query correctly reconstructs partial-range answers by combining the node’s own tag contribution with its children’s. Node count. Each add call recurses into at most 2 children per level (both branches fire only when $[x,y)$ straddles the midpoint) but creates a new node only the first time that child is visited; across the $O(\log C)$ levels of a single add, at most 2 new nodes are created per level along the boundary of $[x,y)$ (interior fully-covered subtrees stop recursing and never allocate), giving $O(\log C)$ new nodes per update. $■$

Tested against a direct array simulation of range-add/range-sum on random coordinate ranges and operations — all match.

• Each update creates at most $2{\log }_{2}C$ nodes. Reserve vectors if the count is predictable.
• Negative coordinates are fine; use l + (r - l) / 2 for the midpoint.
• Take the child index into a local before recursing (push_back may reallocate).
• If all coordinates are known offline, compress them instead: faster and less memory.
• 2D dynamic tree (point add, rectangle sum, online): an outer dynamic tree over $x$, each node owning a dynamic inner tree over $y$; $O(\log X\log Y)$ per operation and memory per point. Offline, a compressed 2D Fenwick is about 10x lighter.

Persistent segment tree

struct PSeg {
    int n; vector<int> L{0}, R{0}; vector<ll> S{0};    // node 0 = empty tree, children are itself
    PSeg(int n) : n(n) {}
    int add(int p, int l, int r, int pos, ll v) {
        int q = sz(L); L.push_back(L[p]); R.push_back(R[p]); S.push_back(S[p] + v);
        if (r - l > 1) {
            int m = (l + r) / 2;
            if (pos < m) { int c = add(L[p], l, m, pos, v); L[q] = c; }
            else { int c = add(R[p], m, r, pos, v); R[q] = c; }
        }
        return q;
    }
    ll sum(int p, int l, int r, int x, int y) const {
        if (!p || y <= l || r <= x) return 0;
        if (x <= l && r <= y) return S[p];
        int m = (l + r) / 2;
        return sum(L[p], l, m, x, y) + sum(R[p], m, r, x, y);
    }
    int kth(int a, int b, ll k) const {                // k-th (0-indexed) of version b minus version a
        int l = 0, r = n;
        while (r - l > 1) {
            int m = (l + r) / 2; ll c = S[L[b]] - S[L[a]];
            if (k < c) a = L[a], b = L[b], r = m; else k -= c, a = R[a], b = R[b], l = m;
        }
        return l;
    }
};

Proof: persistence, range sum, and kth are correct

Persistence. add(p,...) never mutates node p; it allocates a fresh node q copying p’s current L[p],R[p],S[p] and then overwrites only the one child pointer (L[q] or R[q]) on the path to pos, recursing with the old child p’s corresponding child as the base to copy from next. So every call produces a new root whose subtree shares every node not on the root-to-leaf path with the old version, and the old root (and everything reachable from it) is untouched — both versions remain independently queryable. Exactly one new node is created per level, so $O(\log n)$ new nodes per update. Range sum. S[q] = S[p]+v at every node on the copied path means S[p] for any node is the total weight in its range as of that version — identical to an ordinary non-persistent segment tree’s invariant, just computed on an immutable snapshot — so sum(p,...) is the standard segment-tree range-sum recursion, correct by the same argument as the plain tree. Version difference. Since $S$ at any shared (un-copied) node is identical between two versions, $S[L[b]]-S[L[a]]$ computes exactly the weight added to the left half between version $a$ and version $b$, with no double-counting of the shared structure. kth. This is binary search on the implicit “weight by value” distribution of (version $b$ minus version $a$): at each step, the left subtree holds $c=S[L[b]]-S[L[a]]$ of the remaining weight; if $k<c$ the answer lies in the left half (recurse into both versions’ left children, same range halving as an ordinary persistent order-statistics tree), else subtract $c$ and recurse right — correct by the standard Fenwick/segment-tree order-statistics descent argument, here applied to a difference of two snapshots rather than one. $■$

Tested against a brute-force array simulation: range-sum between arbitrary version pairs, and kth against a linear cumulative-weight scan — all match.

Persistent lazy (range add): with tag permanence, an update copies only the $O(\log n)$ nodes it visits and adds the tag to fully covered copies; queries accumulate tag * overlap along the way. “Go back to version $t$” is just roots.push_back(roots[t]) (SPOJ TTM “To the moon”). With push-down tags you’d have to copy children on every push, which doubles memory but works for non-commutative tags.

Point assign on a sum-only tree: there’s no separate “set” operation above, but one is free: add(root, pos, v - sum(root, pos, pos + 1)) adds exactly the difference needed to make the point equal $v$. For $k$-th-smallest-by-value queries on a static array, a wavelet matrix answers the same questions with less memory and no persistence machinery — reach for it instead when every version isn’t actually needed.

What they solve

Problem	Tool
$k$-th smallest / count in value range of $a[l..r]$, online	persistent tree over values, versions = prefixes
number of distinct values in $a[l..r]$, online	persistent tree over positions keeping only last occurrences
queries on old versions after range updates	persistent lazy tree
point updates on a $10^{18}$ line	dynamic tree
$k$-th smallest on a tree path	persistent tree versions along root paths: $u+v-\text{lca}-\text{parent(lca)}$
“how many of the first $k$ updates affect position $x$“	persistence over the update sequence
merging and splitting sets of values	dynamic trees with merge/split (Merging and Splitting)

Memory: about (updates) $\times (\lceil {\log }_{2}n\rceil +2)$ nodes. At $2\cdot 10^5$ updates and $n=2\cdot 10^5$ that’s 4 million nodes, fine. Persistent lazy trees with large ranges can need 50+ million nodes, so estimate first.