Persistent Data Structures

A persistent structure keeps every historical version accessible. The trick is path copying: an update copies only the $O(\log n)$ nodes on the path it modifies, sharing everything else with the previous version.

Persistent segment tree

struct Node { int l = 0, r = 0; long long sum = 0; };
vector<Node> t{Node{}};                              // node 0 = the null node
vector<int> root;                                    // root[v] = version v
 
int build(int l, int r) {
    int cur = t.size(); t.push_back({});
    if (l == r) return cur;
    int m = (l + r) / 2;
    t[cur].l = build(l, m);
    t[cur].r = build(m + 1, r);
    return cur;
}
 
int update(int prev, int l, int r, int pos, long long val) {
    int cur = t.size(); t.push_back(t[prev]);        // COPY the old node
    if (l == r) { t[cur].sum += val; return cur; }
    int m = (l + r) / 2;
    if (pos <= m) t[cur].l = update(t[prev].l, l, m, pos, val);
    else          t[cur].r = update(t[prev].r, m + 1, r, pos, val);
    t[cur].sum = t[t[cur].l].sum + t[t[cur].r].sum;
    return cur;
}
 
long long query(int node, int l, int r, int ql, int qr) {
    if (qr < l || r < ql || !node) return 0;
    if (ql <= l && r <= qr) return t[node].sum;
    int m = (l + r) / 2;
    return query(t[node].l, l, m, ql, qr) + query(t[node].r, m + 1, r, ql, qr);
}

$O(\log n)$ time and $O(\log n)$ new nodes per update. Total memory $O((n+q)\log n)$.

The killer application: $k$-th smallest in a range

Build version $i$ by inserting $a_i$ into version $i-1$, indexed by value. Then version $r$ minus version $l-1$ is a segment tree over the values present in $[l,r]$ — and descending it gives the $k$-th smallest in $O(\log n)$.

int kth(int u, int v, int l, int r, int k) {        // u = root[l-1], v = root[r]
    if (l == r) return l;
    int leftCount = t[t[v].l].sum - t[t[u].l].sum;
    int m = (l + r) / 2;
    if (k <= leftCount) return kth(t[u].l, t[v].l, l, m, k);
    return kth(t[u].r, t[v].r, m + 1, r, k - leftCount);
}

Subtracting two versions is the central idea — it works because the trees have identical shape, so corresponding nodes can be walked in lockstep. This pattern also gives:

• count of elements $\le x$ in $[l,r]$,
• number of distinct values in $[l,r]$ (with a “last occurrence” formulation),
• sum of the $k$ smallest in $[l,r]$,
• range mode and quantile queries.

The persistent family

Structure	Update	Memory per update	Use
Persistent segment tree	$O(\log n)$	$O(\log n)$	range $k$-th, historical queries
Persistent array	$O(\log n)$	$O(\log n)$	the primitive under everything else
Persistent trie	$O(B)$	$O(B)$	max XOR over an index range
Persistent treap	$O(\log n)$ am.	$O(\log n)$	versioned sequences with insert/erase
Persistent DSU	$O({\log }^{2}n)$	$O(\log n)$	connectivity at any point in history
Persistent heap	$O(\log n)$	$O(\log n)$	Eppstein’s k shortest paths

Full vs partial persistence

• Partial persistence — old versions are readable but only the newest is writable. This is what path copying gives, and it covers essentially every contest use.
• Full persistence — any version can be updated, producing a version tree. Also achievable with path copying; you just keep a root per version and never assume a linear order.

Memory

The binding constraint. $(n+q)\log n$ nodes at 12-16 bytes each: for $n=q=2\cdot 10^5$ and $\log n=18$, that is $7\cdot 10^6$ nodes ≈ 100 MB. Mitigations:

• Skip the initial build — start from an empty tree with implicit null children (node 0).
• Use int for child indices, not pointers.
• Preallocate the node array with reserve to avoid reallocation.
• Store only what you need in each node.

When to prefer something else

• Queries known in advance → an offline BIT sweep is $O(n)$ memory and faster.
• Only the latest version matters → an ordinary segment tree.
• Memory is very tight and you need range $k$-th → a wavelet tree uses bits instead of integers.

See also: Segment Tree · Wavelet Tree · K-th Order Statistics