Persistent Data Structures (Persistent Segment Tree)
Persistent Data Structures preserve all historical versions after every update using path copying, allowing O(log n) versioned queries and static range k-th smallest element queries.
Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code
Persistent Data Structures (Persistent Segment Tree)
A Persistent Data Structure preserves every previous version whenever it is modified! Instead of copying an entire $O(n)$ tree on an update, Path Copying only allocates the $O(\log n)$ nodes along the root-to-leaf path that actually changed, sharing all unmodified subtrees with the previous version! Building a Persistent Segment Tree over prefixes 0..i solves "find the $k$-th smallest element in A[L..R]" in $O(\log n)$ per query!
At a Glance
| Property | Value |
| :--- | :---: |
| Update Time & Space per Version | $O(\log n)$ new nodes |
| Total Space after $q$ Updates | $O(n + q \log n)$ |
| Range $k$-th Smallest Query [L, R] | $O(\log n)$ (subtract version root[L - 1] from root[R]) |
---
Practice Problems
Hard
1. Static Range $k$-th Smallest Element (SPOJ MKTHNUM)
Given an array A[0..n-1], answer queries: what is the $k$-th smallest element in A[l..r] (1-indexed k) in $O(\log n)$ time!
Approach: Coordinate-compress A to 0..m-1. Build root[i + 1] = update(root[i], rank[A[i]], +1). To query [l, r], walk root[r + 1] and root[l] in lockstep: the number of elements in the left value-half is leftCount = tree[L(r+1)].cnt - tree[L(l)].cnt! Time: $O((n + q)\log n)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <vector>
struct PNode { int l = 0, r = 0, cnt = 0; };
struct PersistentSegTree {
int m;
std::vector<PNode> t;
std::vector<int> roots;
explicit PersistentSegTree(int distinctVals) : m(distinctVals) {
t.push_back({0, 0, 0}); // null node 0
roots.push_back(0);
}
int update(int prev, int l, int r, int pos) {
int cur = static_cast<int>(t.size());
t.push_back(t[prev]);
++t[cur].cnt;
if (l < r) {
int mid = (l + r) / 2;
if (pos <= mid) t[cur].l = update(t[prev].l, l, mid, pos);
else t[cur].r = update(t[prev].r, mid + 1, r, pos);
}
return cur;
}
int kth(int u, int v, int l, int r, int k) const {
if (l == r) return l;
int mid = (l + r) / 2;
int leftCnt = t[t[v].l].cnt - t[t[u].l].cnt;
if (k <= leftCnt) return kth(t[u].l, t[v].l, l, mid, k);
return kth(t[u].r, t[v].r, mid + 1, r, k - leftCnt);
}
};
int main() {
std::vector<int> a = {1, 5, 2, 6, 3, 7, 4};
std::vector<int> vals = a;
std::sort(vals.begin(), vals.end());
vals.erase(std::unique(vals.begin(), vals.end()), vals.end());
int m = static_cast<int>(vals.size());
PersistentSegTree pst(m);
for (int x : a) {
int rk = static_cast<int>(std::lower_bound(vals.begin(), vals.end(), x) - vals.begin());
pst.roots.push_back(pst.update(pst.roots.back(), 0, m - 1, rk));
}
// 3rd smallest in a[1..4] = {5, 2, 6, 3} -> sorted {2, 3, 5, 6} -> 5
int rkAns = pst.kth(pst.roots[1], pst.roots[5], 0, m - 1, 3);
std::cout << vals[rkAns] << "\n"; // 5
return 0;
}
</details>
---
Related Structures & Algorithms
- Segment Tree — mutable base structure of a Persistent Segment Tree.