x. Persistent Data Structures

A persistent structure keeps every version. Path copying copies only the $O(\log n)$ nodes an update touches and shares the rest, so each version costs $O(\log n)$ memory. Because versions of a persistent segment tree have the same shape, two versions can be subtracted node by node, which turns prefix versions into range queries.

Proof: path copying gives correct, independent versions at $O(\log n)$ cost each

upd walks root-to-leaf, and at every node on that path allocates a new node (u = sz(t); t.push_back(t[v])) copying the old node’s fields, then overwrites just the one child pointer (l or r) leading further down the path with the new child’s index — the other child pointer is left as-is, pointing at the old, untouched subtree. Since a segment tree over a fixed range has depth $O(\log n)$, exactly $O(\log n)$ new nodes are created per update. Correctness: every node not on the root-to-leaf path is shared verbatim between the old and new version, and since no existing node is ever mutated in place (every write goes to a freshly pushed node), the old version’s root still reaches exactly the same unchanged nodes it did before — old queries against the old root are unaffected by the new version’s existence. The new root reaches the $O(\log n)$ new nodes on the update path (with the one leaf’s value changed and every ancestor’s aggregate recomputed from its two children, one old-untouched and one newly updated) and the shared old nodes everywhere else, so it correctly represents the old array with just that one update applied. $■$

Proof: subtracting two versions' node-wise sums gives the segment tree over the range between them

Since version $i$ is built from version $i-1$ by inserting exactly one value (at the compressed position of $a_i$), every node’s stored sum in version $i$ equals its stored sum in version $i-1$ plus $1$ if $a_i$‘s compressed value falls in that node’s range, else unchanged. By induction, the sum stored at node $N$ (identified by its range $[l,r)$ over compressed values) in version $i$ equals $|\{j\le i:a_j\in [l,r)\}|$ — the count of elements among $a_1,\dots ,a_i$ with value in that range. Both version $r$‘s and version $l-1$‘s trees have identical shape (every update follows the same fixed recursion on the same value-range tree, only the node contents differ), so the same node $N$ exists at the same recursive position in both, and $t[N_r].s-t[N_{l-1}].s=|\{j\le r:a_j\in [l,r)\}|-|\{j\le l-1:a_j\in [l,r)\}|=|\{l\le j\le r:a_j\in [l,r)\}|$ — exactly the count of values in range $[l,r)$ restricted to array positions $[l,r]$. Descending both trees in lockstep (as kth does) therefore walks the segment tree that would have been built from only $a_l,\dots ,a_r$, giving correct order-statistics on that subarray. $■$

Persistent segment tree

struct PST {
    struct N { int l, r; ll s; };
    vector<N> t{{0, 0, 0}};                       // node 0 = empty tree (its children point to itself)
    int upd(int v, int l, int r, int pos, ll d) { // returns the new root
        int u = sz(t); t.push_back(t[v]); t[u].s += d;
        if (r - l > 1) {
            int m = (l + r) / 2;
            if (pos < m) { int c = upd(t[v].l, l, m, pos, d); t[u].l = c; }
            else { int c = upd(t[v].r, m, r, pos, d); t[u].r = c; }
        }
        return u;
    }
    ll sum(int v, int l, int r, int ql, int qr) {
        if (!v || qr <= l || r <= ql) return 0;
        if (ql <= l && r <= qr) return t[v].s;
        int m = (l + r) / 2;
        return sum(t[v].l, l, m, ql, qr) + sum(t[v].r, m, r, ql, qr);
    }
    int kth(int a, int b, int l, int r, ll k) {   // k-th smallest (0-indexed) in version b minus version a
        while (r - l > 1) {
            int m = (l + r) / 2; ll c = t[t[b].l].s - t[t[a].l].s;
            if (k < c) a = t[a].l, b = t[b].l, r = m; else k -= c, a = t[a].r, b = t[b].r, l = m;
        }
        return l;
    }
};

Note: take the child index into a local variable before writing t[u].l = ...: push_back inside the recursive call may reallocate t. Reserve $O((n+q)\log n)$ nodes up front.

Range $k$-th smallest: version $i$ = version $i-1$ plus $a_i$ inserted at its compressed value. Then $[l,r]$ is root[r+1] - root[l], and kth descends in $O(\log n)$. The same subtraction gives count of values in $[x,y]$ within $a[l..r]$, sum of the $k$ smallest, and median.

Distinct values in $a[l..r]$ online: version $r$ has a 1 at the last occurrence (up to $r$) of each value; the answer is the sum over positions $[l,r]$ in version $r$.

Mex of $a[l..r]$ online: a persistent tree over values storing the last position of each value (version $r$); descend to the first value whose last position is $<l$ (store the min in each node).

Other persistent structures

Structure	Cost per update	Typical use
persistent array	$O(\log n)$ (persistent segment tree leaves)	the primitive for persistent DSU, persistent anything
persistent trie	$O(B)$	max XOR with an element of $a[l..r]$
persistent treap / WBLT	$O(\log n)$	versioned sequences, copy-paste of ranges (Treaps)
persistent leftist heap	$O(\log n)$	Eppstein’s $k$ shortest paths
persistent DSU	$O({\log }^{2}n)$	connectivity in any version
persistent lazy segment tree	$O(\log n)$ with tag copying, or permanent tags that are never pushed down	range add on versions (Dynamic and Persistent Segment Trees)
persistent stack/queue	$O(1)$ / $O(1)$ amortized	undo histories

Partial vs full persistence: partial persistence lets every old version be read, but only the newest is writable — a linear history, which covers essentially every contest use. Full persistence lets any version be updated, producing a version tree rather than a line; path copying gives this too, just by keeping a root per version and never assuming a linear order. Amortized structures (splay trees, doubling arrays, union by rank with compression) lose their bounds under persistence because an expensive old state can be reused many times.

Offline alternative: version tree

If all operations are known, put versions in a tree (each version is a child of the version it was derived from), then DFS it with an ordinary structure that supports undo: apply the operation on entry, answer the version’s queries, undo on exit. $O(1)$ extra memory per operation instead of $O(\log n)$, and it works for structures that can’t be made persistent cheaply (DSU, bitsets, knapsack layers).

Memory checklist

• Nodes: $(n+q)\cdot (\lceil {\log }_{2}n\rceil +1)$; for $n=q=2\cdot 10^5$ that’s about $7.6\cdot 10^6$ nodes. With two int children and an int count, 12 bytes each, that’s about 90 MB.
• Don’t build the initial tree; start from the null node 0 whose children are itself.
• Use int indices, not pointers; store only needed fields.
• If memory is tight: wavelet matrix ($n\log \sigma$ bits) for static order statistics, or an offline sweep.

When to prefer something else

Situation	Use instead
queries known in advance	an offline BIT sweep: $O(n)$ memory and faster
only the latest version matters	an ordinary segment tree
memory very tight, need range $k$-th	a wavelet tree — bits instead of integers