These are the notes for Competitive Programming episode 67. A persistent data structure keeps every old version after an update. A segment tree becomes persistent by path copying: an update never changes a node; it creates new copies of the log n + 1 nodes on the path from the root to the changed leaf, and the new nodes point to the old, unchanged subtrees, which are shared. Each version keeps its own root, root[v]. Price Lists (point changes on any old version, range sums in any version) shows the in-place tree losing its history (124 instead of 39), full copies needing 160 GB, and path copying (about 2.5 million nodes for the full limits). Exam Ranks (k-th smallest in a range) builds version i = counts of the first i values (by value), so a range [l, r] is version r minus version l − 1, walked together; using root[l] gives 72 … 90 instead of 61 … 40. Stress tests pass. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook
To fix one line on page 312 of a thick office file, nobody photocopies all 500 pages. The clerk writes a new page 312, a new section index that points to the new page and the old untouched pages, and a new cover index that points to the new section and the old sections: three new sheets. The old cover still opens the old file exactly as it was, and the new cover opens the corrected one. Every version keeps its own cover, and the versions share almost all their pages.
Problem V1 · Price Lists
(Written for this course.)
- Input: n q (n, q ≤ 2 · 10^5), prices a[1..n] (version 0), then q operations:
1 v i x: create a new version from version v with price i set to x (new versions are numbered 1, 2, 3, …);2 v l r: print the total price of items l..r in version v.
5 9
4 8 15 16 23
2 0 1 5
1 0 3 100
2 1 1 5
2 0 2 4
1 1 1 0
1 0 5 -3
2 2 1 3
2 3 1 5
2 0 5 5
Answers: 66, 151, 39, 108, 40, 23.
The obvious attempt: one tree, updated in place (WA)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200001, NODES = 2 * N + 20 * N; // the first tree + about log n per change
int n, q, tot, lc[NODES], rc[NODES], root[N];
ll a[N], sm[NODES];
int build(int lo, int hi) {
int t = ++tot;
if (lo == hi) { sm[t] = a[lo]; return t; }
int mid = (lo + hi) / 2;
lc[t] = build(lo, mid), rc[t] = build(mid + 1, hi);
sm[t] = sm[lc[t]] + sm[rc[t]];
return t;
}
void update(int t, int lo, int hi, int i, ll x) { // change the tree in place
if (lo == hi) { sm[t] = x; return; }
int mid = (lo + hi) / 2;
if (i <= mid) update(lc[t], lo, mid, i, x);
else update(rc[t], mid + 1, hi, i, x);
sm[t] = sm[lc[t]] + sm[rc[t]];
}
ll query(int t, int lo, int hi, int l, int r) {
if (r < lo || hi < l) return 0;
if (l <= lo && hi <= r) return sm[t];
int mid = (lo + hi) / 2;
return query(lc[t], lo, mid, l, r) + query(rc[t], mid + 1, hi, l, r);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
root[0] = build(1, n);
int versions = 1;
while (q--) {
int t, v;
cin >> t >> v;
if (t == 1) {
int i; ll x;
cin >> i >> x;
update(root[v], 1, n, i, x); // changes version v too
root[versions++] = root[v];
}
else { int l, r; cin >> l >> r; cout << query(root[v], 1, n, l, r) << "\n"; }
}
}
66
151
124
108
121
-3
Version 0's items 2..4 must still cost 8 + 15 + 16 = 39, but the change made for version 1 overwrote the shared tree.
Full copies (MLE)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q;
vector<vector<ll>> ver; // every version, a full copy
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
ver.push_back(vector<ll>(n + 1));
for (int i = 1; i <= n; i++) cin >> ver[0][i];
while (q--) {
int t, v;
cin >> t >> v;
if (t == 1) { int i; ll x; cin >> i >> x; ver.push_back(ver[v]); ver.back()[i] = x; }
else {
int l, r;
cin >> l >> r;
cout << accumulate(ver[v].begin() + l, ver[v].begin() + r + 1, 0LL) << "\n";
}
}
cout << "memory: " << ver.size() * (n + 1) * 8 << " bytes\n";
}
66
151
39
108
40
23
memory: 192 bytes
For the real limits (half of the operations create versions), the same memory count:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q;
int main() {
n = q = 200000; // the real limits, half of them changes
ll versions = q / 2 + 1;
cout << "memory: " << versions * (n + 1) * 8 << " bytes\n";
}
memory: 160002400008 bytes
160 GB against a typical 256 MB limit: Memory Limit Exceeded by a factor of about 600.
Path copying
A point update only changes the totals on one root-to-leaf path. So:
- nodes live in arrays
lc[t],rc[t],sm[t](shared nodes can't use the 2i / 2i + 1 numbering); update(old, …)returns a new nodet = ++totthat copiesold's children, replaces one side with a recursive update, and recomputessm[t];- a new version is
root[versions++] = update(root[v], 1, n, i, x); old roots are untouched.
On prices 4 8 15 16, changing price 3 to 100 creates a new leaf (100), a new node for 3–4 (116) and a new root (128); the new nodes point to the old left half and the old leaf 4.
Memory: about 2n nodes for version 0 plus (log n + 1) per change, about 4 · 10^6 nodes here.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200001, NODES = 2 * N + 20 * N; // the first tree + about log n per change
int n, q, tot, lc[NODES], rc[NODES], root[N];
ll a[N], sm[NODES];
int build(int lo, int hi) {
int t = ++tot;
if (lo == hi) { sm[t] = a[lo]; return t; }
int mid = (lo + hi) / 2;
lc[t] = build(lo, mid), rc[t] = build(mid + 1, hi);
sm[t] = sm[lc[t]] + sm[rc[t]];
return t;
}
int update(int old, int lo, int hi, int i, ll x) { // returns a NEW node
int t = ++tot;
lc[t] = lc[old], rc[t] = rc[old]; // copy the old node
if (lo == hi) { sm[t] = x; return t; }
int mid = (lo + hi) / 2;
if (i <= mid) lc[t] = update(lc[old], lo, mid, i, x); // new path on one side
else rc[t] = update(rc[old], mid + 1, hi, i, x); // the other side is shared
sm[t] = sm[lc[t]] + sm[rc[t]];
return t;
}
ll query(int t, int lo, int hi, int l, int r) {
if (r < lo || hi < l) return 0;
if (l <= lo && hi <= r) return sm[t];
int mid = (lo + hi) / 2;
return query(lc[t], lo, mid, l, r) + query(rc[t], mid + 1, hi, l, r);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
root[0] = build(1, n);
int versions = 1;
while (q--) {
int t, v;
cin >> t >> v;
if (t == 1) {
int i; ll x;
cin >> i >> x;
root[versions++] = update(root[v], 1, n, i, x); // a new root
}
else { int l, r; cin >> l >> r; cout << query(root[v], 1, n, l, r) << "\n"; }
}
}
66
151
39
108
40
23
One item, changed, then asked in both versions:
1 3
7
1 0 1 9
2 1 1 1
2 0 1 1
9
7
The full limits: 10^5 changes to random older versions and 10^5 questions (xor of the answers, then the number of nodes used):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200001, NODES = 2 * N + 20 * N; // the first tree + about log n per change
int n, q, tot, lc[NODES], rc[NODES], root[N];
ll a[N], sm[NODES];
int build(int lo, int hi) {
int t = ++tot;
if (lo == hi) { sm[t] = a[lo]; return t; }
int mid = (lo + hi) / 2;
lc[t] = build(lo, mid), rc[t] = build(mid + 1, hi);
sm[t] = sm[lc[t]] + sm[rc[t]];
return t;
}
int update(int old, int lo, int hi, int i, ll x) { // returns a NEW node
int t = ++tot;
lc[t] = lc[old], rc[t] = rc[old]; // copy the old node
if (lo == hi) { sm[t] = x; return t; }
int mid = (lo + hi) / 2;
if (i <= mid) lc[t] = update(lc[old], lo, mid, i, x); // new path on one side
else rc[t] = update(rc[old], mid + 1, hi, i, x); // the other side is shared
sm[t] = sm[lc[t]] + sm[rc[t]];
return t;
}
ll query(int t, int lo, int hi, int l, int r) {
if (r < lo || hi < l) return 0;
if (l <= lo && hi <= r) return sm[t];
int mid = (lo + hi) / 2;
return query(lc[t], lo, mid, l, r) + query(rc[t], mid + 1, hi, l, r);
}
int main() {
n = q = 200000;
mt19937 rng(67);
for (int i = 1; i <= n; i++) a[i] = rng() % 1000000;
root[0] = build(1, n);
int versions = 1;
ll check = 0;
for (int k = 0; k < q; k++) {
int v = rng() % versions; // any older version
if (k % 2 == 0) root[versions++] = update(root[v], 1, n, rng() % n + 1, rng() % 1000000);
else {
int l = rng() % n + 1, r = rng() % n + 1;
if (l > r) swap(l, r);
check ^= query(root[v], 1, n, l, r);
}
}
cout << check << " · nodes used: " << tot << "\n";
}
63135914924 · nodes used: 2268937
Stress test (against full copies on small arrays)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200001, NODES = 2 * N + 20 * N; // the first tree + about log n per change
int n, q, tot, lc[NODES], rc[NODES], root[N];
ll a[N], sm[NODES];
int build(int lo, int hi) {
int t = ++tot;
if (lo == hi) { sm[t] = a[lo]; return t; }
int mid = (lo + hi) / 2;
lc[t] = build(lo, mid), rc[t] = build(mid + 1, hi);
sm[t] = sm[lc[t]] + sm[rc[t]];
return t;
}
int update(int old, int lo, int hi, int i, ll x) { // returns a NEW node
int t = ++tot;
lc[t] = lc[old], rc[t] = rc[old]; // copy the old node
if (lo == hi) { sm[t] = x; return t; }
int mid = (lo + hi) / 2;
if (i <= mid) lc[t] = update(lc[old], lo, mid, i, x); // new path on one side
else rc[t] = update(rc[old], mid + 1, hi, i, x); // the other side is shared
sm[t] = sm[lc[t]] + sm[rc[t]];
return t;
}
ll query(int t, int lo, int hi, int l, int r) {
if (r < lo || hi < l) return 0;
if (l <= lo && hi <= r) return sm[t];
int mid = (lo + hi) / 2;
return query(lc[t], lo, mid, l, r) + query(rc[t], mid + 1, hi, l, r);
}
int main() {
mt19937 rng(67);
for (int t = 1; t <= 300; t++) {
n = rng() % 30 + 1, tot = 0;
vector<vector<ll>> ver(1, vector<ll>(n + 1));
for (int i = 1; i <= n; i++) ver[0][i] = a[i] = rng() % 100;
root[0] = build(1, n);
for (int k = 0; k < 60; k++) {
int v = rng() % ver.size(), l = rng() % n + 1, r = rng() % n + 1;
if (l > r) swap(l, r);
if (k % 2) {
ll x = rng() % 100;
root[ver.size()] = update(root[v], 1, n, l, x);
ver.push_back(ver[v]), ver.back()[l] = x;
}
else if (query(root[v], 1, n, l, r) != accumulate(&ver[v][l], &ver[v][r] + 1, 0LL)) {
cout << "mismatch on test " << t;
return 0;
}
}
}
cout << "all 300 tests passed";
}
all 300 tests passed
Problem V2 · Exam Ranks
(Written for this course, in the style of the classic "k-th number in a range" problem.)
- Input: n q (n, q ≤ 2 · 10^5), marks a[1..n] (≤ 10^9) in roll-number order, then q queries l r k.
- Output per query: the k-th lowest mark among rolls l..r.
7 4
55 90 72 40 90 61 80
1 7 3
2 5 1
3 6 4
4 4 1
Answers: 61, 40, 90, 40.
Idea. Compress the marks to ranks 1..m. Build a segment tree over ranks whose leaves count students. Version i = version i − 1 plus student i (a persistent insert of one path, adding 1 to each count on it). Then the students l..r are exactly version r minus version l − 1, like prefix sums of whole trees. To find the k-th: at each node, left = cnt[lc[v]] − cnt[lc[u]] (u = root[l − 1], v = root[r]); if k ≤ left go left, otherwise k −= left and go right. Node 0 is the empty tree (lc[0] = rc[0] = 0, cnt[0] = 0), so version 0 needs no build.
The obvious attempt: sort per query (TLE)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q, a[200001];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
while (q--) {
int l, r, k;
cin >> l >> r >> k;
vector<int> b(a + l, a + r + 1); // copy the range
sort(b.begin(), b.end());
cout << b[k - 1] << "\n";
}
}
61
40
90
40
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q, a[200001];
int main() {
n = q = 200000;
mt19937 rng(67);
for (int i = 1; i <= n; i++) a[i] = rng() % 1000000000;
ll check = 0;
for (int t = 0; t < q; t++) {
int l = rng() % n + 1, r = rng() % n + 1;
if (l > r) swap(l, r);
int k = rng() % (r - l + 1) + 1;
vector<int> b(a + l, a + r + 1);
sort(b.begin(), b.end());
check += b[k - 1];
}
cout << check << "\n";
}
Time Limit Exceeded
The bug: root[l] instead of root[l − 1]
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200001, NODES = 20 * N; // node 0 = the empty tree
int n, q, m, tot, a[N], vals[N], lc[NODES], rc[NODES], cnt[NODES], root[N];
int insert(int old, int lo, int hi, int p) { // one more mark with rank p
int t = ++tot;
lc[t] = lc[old], rc[t] = rc[old], cnt[t] = cnt[old] + 1;
if (lo == hi) return t;
int mid = (lo + hi) / 2;
if (p <= mid) lc[t] = insert(lc[old], lo, mid, p);
else rc[t] = insert(rc[old], mid + 1, hi, p);
return t;
}
int kth(int u, int v, int lo, int hi, int k) { // tree v minus tree u
if (lo == hi) return lo;
int mid = (lo + hi) / 2, left = cnt[lc[v]] - cnt[lc[u]];
if (k <= left) return kth(lc[u], lc[v], lo, mid, k);
return kth(rc[u], rc[v], mid + 1, hi, k - left);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) vals[i - 1] = a[i];
sort(vals, vals + n);
m = unique(vals, vals + n) - vals; // coordinate compression
for (int i = 1; i <= n; i++)
root[i] = insert(root[i - 1], 1, m, lower_bound(vals, vals + m, a[i]) - vals + 1);
while (q--) {
int l, r, k;
cin >> l >> r >> k;
cout << vals[kth(root[l], root[r], 1, m, k) - 1] << "\n";
}
}
72
40
90
90
Expected 61 40 90 40: subtracting version l leaves student l out.
The fix
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200001, NODES = 20 * N; // node 0 = the empty tree
int n, q, m, tot, a[N], vals[N], lc[NODES], rc[NODES], cnt[NODES], root[N];
int insert(int old, int lo, int hi, int p) { // one more mark with rank p
int t = ++tot;
lc[t] = lc[old], rc[t] = rc[old], cnt[t] = cnt[old] + 1;
if (lo == hi) return t;
int mid = (lo + hi) / 2;
if (p <= mid) lc[t] = insert(lc[old], lo, mid, p);
else rc[t] = insert(rc[old], mid + 1, hi, p);
return t;
}
int kth(int u, int v, int lo, int hi, int k) { // tree v minus tree u
if (lo == hi) return lo;
int mid = (lo + hi) / 2, left = cnt[lc[v]] - cnt[lc[u]];
if (k <= left) return kth(lc[u], lc[v], lo, mid, k);
return kth(rc[u], rc[v], mid + 1, hi, k - left);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) vals[i - 1] = a[i];
sort(vals, vals + n);
m = unique(vals, vals + n) - vals; // coordinate compression
for (int i = 1; i <= n; i++)
root[i] = insert(root[i - 1], 1, m, lower_bound(vals, vals + m, a[i]) - vals + 1);
while (q--) {
int l, r, k;
cin >> l >> r >> k;
cout << vals[kth(root[l - 1], root[r], 1, m, k) - 1] << "\n";
}
}
61
40
90
40
The full limits (sum of the answers as a check number):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200001, NODES = 20 * N; // node 0 = the empty tree
int n, q, m, tot, a[N], vals[N], lc[NODES], rc[NODES], cnt[NODES], root[N];
int insert(int old, int lo, int hi, int p) { // one more mark with rank p
int t = ++tot;
lc[t] = lc[old], rc[t] = rc[old], cnt[t] = cnt[old] + 1;
if (lo == hi) return t;
int mid = (lo + hi) / 2;
if (p <= mid) lc[t] = insert(lc[old], lo, mid, p);
else rc[t] = insert(rc[old], mid + 1, hi, p);
return t;
}
int kth(int u, int v, int lo, int hi, int k) { // tree v minus tree u
if (lo == hi) return lo;
int mid = (lo + hi) / 2, left = cnt[lc[v]] - cnt[lc[u]];
if (k <= left) return kth(lc[u], lc[v], lo, mid, k);
return kth(rc[u], rc[v], mid + 1, hi, k - left);
}
int main() {
n = q = 200000;
mt19937 rng(67);
for (int i = 1; i <= n; i++) a[i] = rng() % 1000000000;
for (int i = 1; i <= n; i++) vals[i - 1] = a[i];
sort(vals, vals + n);
m = unique(vals, vals + n) - vals; // coordinate compression
for (int i = 1; i <= n; i++)
root[i] = insert(root[i - 1], 1, m, lower_bound(vals, vals + m, a[i]) - vals + 1);
ll check = 0;
for (int t = 0; t < q; t++) {
int l = rng() % n + 1, r = rng() % n + 1;
if (l > r) swap(l, r);
int k = rng() % (r - l + 1) + 1;
check += vals[kth(root[l - 1], root[r], 1, m, k) - 1];
}
cout << check << "\n";
}
95371945252374
Stress test (against nth_element)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200001, NODES = 20 * N; // node 0 = the empty tree
int n, q, m, tot, a[N], vals[N], lc[NODES], rc[NODES], cnt[NODES], root[N];
int insert(int old, int lo, int hi, int p) { // one more mark with rank p
int t = ++tot;
lc[t] = lc[old], rc[t] = rc[old], cnt[t] = cnt[old] + 1;
if (lo == hi) return t;
int mid = (lo + hi) / 2;
if (p <= mid) lc[t] = insert(lc[old], lo, mid, p);
else rc[t] = insert(rc[old], mid + 1, hi, p);
return t;
}
int kth(int u, int v, int lo, int hi, int k) { // tree v minus tree u
if (lo == hi) return lo;
int mid = (lo + hi) / 2, left = cnt[lc[v]] - cnt[lc[u]];
if (k <= left) return kth(lc[u], lc[v], lo, mid, k);
return kth(rc[u], rc[v], mid + 1, hi, k - left);
}
int main() {
mt19937 rng(67);
for (int t = 1; t <= 500; t++) {
n = rng() % 30 + 1, tot = 0;
for (int i = 1; i <= n; i++) a[i] = rng() % 20;
for (int i = 1; i <= n; i++) vals[i - 1] = a[i];
sort(vals, vals + n);
m = unique(vals, vals + n) - vals; // coordinate compression
for (int i = 1; i <= n; i++)
root[i] = insert(root[i - 1], 1, m, lower_bound(vals, vals + m, a[i]) - vals + 1);
for (int k = 0; k < 30; k++) {
int l = rng() % n + 1, r = rng() % n + 1;
if (l > r) swap(l, r);
int x = rng() % (r - l + 1) + 1;
vector<int> b(a + l, a + r + 1);
nth_element(b.begin(), b.begin() + x - 1, b.end());
if (vals[kth(root[l - 1], root[r], 1, m, x) - 1] != b[x - 1]) {
cout << "mismatch on test " << t;
return 0;
}
}
}
cout << "all 500 tests passed";
}
all 500 tests passed
Complexity vs the constraints
| Method | Time | Memory | Verdict |
|---|---|---|---|
| V1: one tree in place | O(log n) | O(n) | WA (history lost) |
| V1: full copies | O(n) per version | O(n · q) ≈ 160 GB | MLE |
| V1: path copying | O(log n) per change and query | O(n + q log n) ≈ 4 · 10^6 nodes | accepted |
| V2: sort per query | O(n log n) per query | O(n) | TLE |
| V2: persistent tree over ranks | O(n log n) build, O(log n) per query | O(n log n) | accepted |
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| updating in place | 124 (expected 39) |
old versions overwritten | a new node per change |
| full copies | 160 GB | O(n) per version | path copying |
root[l] instead of root[l − 1] |
72 … 90 (expected 61 … 40) |
element l left out | root[l − 1] |
| node pool too small | Runtime Error / garbage | ≈ log n + 1 new nodes per change | about 20 · n nodes |
| children as 2i, 2i + 1 | wrong sums | nodes are shared | store lc, rc |
| forgetting compression | huge tree / MLE | values up to 10^9 | sort + unique + lower_bound |
| recursion on deep trees in Java/Python | stack overflow | log n is fine, but avoid O(n) recursion | iterative walks |
Mini project
Build a PersistentSegTree class with update(version, i, x) returning a new version and query(version, l, r), then add an undo command that jumps back to any earlier version (homework 2). Use it to answer "k-th smallest", "count ≤ x" (homework 1) and "median of a range" (homework 4), and stress-test each against sorting.
Practice
These are the homework problems from the episode. The C++ solution was checked against a brute force on 300 random tests.
1. Count values ≤ x in l..r.
Solution
Same versions as V2. Convert x to the number of ranks with value ≤ x (upper_bound), then add up cnt[v] − cnt[u] over the nodes covering ranks 1..p.
#include <bits/stdc++.h>
using namespace std;
const int N = 200001, NODES = 20 * N; // node 0 = the empty tree
int n, q, m, tot, a[N], vals[N], lc[NODES], rc[NODES], cnt[NODES], root[N];
int insert(int old, int lo, int hi, int p) {
int t = ++tot;
lc[t] = lc[old], rc[t] = rc[old], cnt[t] = cnt[old] + 1;
if (lo == hi) return t;
int mid = (lo + hi) / 2;
if (p <= mid) lc[t] = insert(lc[old], lo, mid, p);
else rc[t] = insert(rc[old], mid + 1, hi, p);
return t;
}
int countUpTo(int u, int v, int lo, int hi, int p) { // ranks 1..p in tree v minus tree u
if (p < lo) return 0;
if (hi <= p) return cnt[v] - cnt[u];
int mid = (lo + hi) / 2;
return countUpTo(lc[u], lc[v], lo, mid, p) + countUpTo(rc[u], rc[v], mid + 1, hi, p);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i], vals[i - 1] = a[i];
sort(vals, vals + n);
m = unique(vals, vals + n) - vals;
for (int i = 1; i <= n; i++)
root[i] = insert(root[i - 1], 1, m, lower_bound(vals, vals + m, a[i]) - vals + 1);
while (q--) {
int l, r, x;
cin >> l >> r >> x;
int p = upper_bound(vals, vals + m, x) - vals; // ranks with value <= x
cout << countUpTo(root[l - 1], root[r], 1, m, p) << "\n";
}
}
7 4
55 90 72 40 90 61 80
1 7 70
2 5 90
3 6 50
4 4 39
3
4
1
0
2. Undo: go back to version v.
Solution
Nothing to undo: old versions never change. Keep a cur index; "undo to v" is root[next] = root[v] (or just cur = v). That's the whole point of persistence.
3. Distinct values in l..r, online.
Solution
For each position i, let prev[i] be the previous position with the same value (0 if none). The distinct values in [l, r] are the positions i in [l, r] with prev[i] < l. Build version i by inserting prev[i] for the first i elements (a tree over positions 0..n); the answer is the count of values < l in version r minus version l − 1. Each query is O(log n) and can be answered online, unlike Mo's algorithm.
4. The median of every range.
Solution
It's the k-th smallest with k = (r − l + 2) / 2 (the lower median), so V2's code answers it directly.
Quick quiz
n = 2^17 items. One persistent point update creates how many new nodes?
A) 18 · B) 17 · C) 2^17 · D) 1
Answer
A. The tree has 17 levels below the root, so a root-to-leaf path has 18 nodes; each is copied once.
Interview questions
- What is a persistent data structure? One where updates create new versions and every old version stays available and unchanged.
- How does a persistent segment tree work? Path copying: an update copies the O(log n) nodes on one root-to-leaf path; everything else is shared; each version has its own root.
- Memory per update? log n + 1 new nodes.
- How do you find the k-th smallest in a range? Versions over values (prefix i = first i elements), then walk root[r] and root[l − 1] together, comparing left-child count differences with k.
- Why can't nodes use 2i / 2i + 1? Because a node can be the child of many parents in different versions; children must be stored explicitly.
- Persistent tree vs Mo's algorithm for range queries? Persistent trees answer online in O(log n) with more memory; Mo's needs offline queries but little memory.
- What's the "empty tree" trick? Node 0 with lc = rc = 0 and count 0 acts as a complete empty tree, so version 0 needs no build.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Version | A saved state of the data | price list version 2 |
| Persistent | Keeps every old version unchanged | root[0] still works |
| Path copying | Copying only the root-to-leaf path that changes | 3 new nodes for n = 4 |
| Shared subtree | A node used by several versions | the left half 1–2 |
root[v] |
The root node of version v | one per version |
| Node pool | Arrays lc, rc, sm/cnt with a counter tot |
t = ++tot |
lc, rc |
A node's left and right child | explicit links |
| In-place update | Changing nodes directly | loses history |
| MLE | Memory Limit Exceeded | 160 GB |
| Coordinate compression | Mapping values to ranks 1..m | marks → ranks |
| Tree over values | Leaves are values (ranks), storing counts | V2 |
| Prefix versions | Version i holds the first i elements | root[i] |
| k-th smallest | The value at position k after sorting | 3rd lowest mark |
| Empty tree (node 0) | A node whose children are itself, count 0 | root[0] = 0 |
nth_element |
Puts the k-th smallest at position k in O(n) on average | the stress test |
| Stress test | Comparing a fast solution with a slow, surely-correct one on many random inputs | all 500 tests passed |
| Wrong Answer (WA) | A wrong output | 124 |
| Time Limit Exceeded (TLE) | Too slow | sort per query |
| Ordered set | g++'s order statistics tree | next episode |
Summary
- Persistent = old versions never change; path copying = log n + 1 new nodes per update; root[v] per version.
- Store children explicitly (
lc,rc); size the node pool at about 20 · n. - Versions over values answer order questions: range [l, r] = root[r] − root[l − 1].
- k-th smallest: walk both versions, compare
cnt[lc[v]] − cnt[lc[u]]with k: O(log n), online.
Solutions in C++, Java and Python
Problem V1 · Price Lists
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200001, NODES = 2 * N + 20 * N; // the first tree + about log n per change
int n, q, tot, lc[NODES], rc[NODES], root[N];
ll a[N], sm[NODES];
int build(int lo, int hi) {
int t = ++tot;
if (lo == hi) { sm[t] = a[lo]; return t; }
int mid = (lo + hi) / 2;
lc[t] = build(lo, mid), rc[t] = build(mid + 1, hi);
sm[t] = sm[lc[t]] + sm[rc[t]];
return t;
}
int update(int old, int lo, int hi, int i, ll x) { // returns a NEW node
int t = ++tot;
lc[t] = lc[old], rc[t] = rc[old]; // copy the old node
if (lo == hi) { sm[t] = x; return t; }
int mid = (lo + hi) / 2;
if (i <= mid) lc[t] = update(lc[old], lo, mid, i, x); // new path on one side
else rc[t] = update(rc[old], mid + 1, hi, i, x); // the other side is shared
sm[t] = sm[lc[t]] + sm[rc[t]];
return t;
}
ll query(int t, int lo, int hi, int l, int r) {
if (r < lo || hi < l) return 0;
if (l <= lo && hi <= r) return sm[t];
int mid = (lo + hi) / 2;
return query(lc[t], lo, mid, l, r) + query(rc[t], mid + 1, hi, l, r);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
root[0] = build(1, n);
int versions = 1;
while (q--) {
int t, v;
cin >> t >> v;
if (t == 1) {
int i; ll x;
cin >> i >> x;
root[versions++] = update(root[v], 1, n, i, x); // a new root
}
else { int l, r; cin >> l >> r; cout << query(root[v], 1, n, l, r) << "\n"; }
}
}
66
151
39
108
40
23
Java
import java.util.*;
import java.io.*;
public class Main {
static int tot = 0;
static int[] lc, rc;
static long[] sm, a;
static int build(int lo, int hi) {
int t = ++tot;
if (lo == hi) { sm[t] = a[lo]; return t; }
int mid = (lo + hi) / 2;
lc[t] = build(lo, mid); rc[t] = build(mid + 1, hi);
sm[t] = sm[lc[t]] + sm[rc[t]];
return t;
}
static int update(int old, int lo, int hi, int i, long x) { // returns a NEW node
int t = ++tot;
lc[t] = lc[old]; rc[t] = rc[old];
if (lo == hi) { sm[t] = x; return t; }
int mid = (lo + hi) / 2;
if (i <= mid) lc[t] = update(lc[old], lo, mid, i, x);
else rc[t] = update(rc[old], mid + 1, hi, i, x);
sm[t] = sm[lc[t]] + sm[rc[t]];
return t;
}
static long query(int t, int lo, int hi, int l, int r) {
if (r < lo || hi < l) return 0;
if (l <= lo && hi <= r) return sm[t];
int mid = (lo + hi) / 2;
return query(lc[t], lo, mid, l, r) + query(rc[t], mid + 1, hi, l, r);
}
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedInputStream(System.in));
in.nextToken(); int n = (int) in.nval; in.nextToken(); int q = (int) in.nval;
a = new long[n + 1];
for (int i = 1; i <= n; i++) { in.nextToken(); a[i] = (long) in.nval; }
int nodes = 2 * n + 20 * (q + 1) + 5;
lc = new int[nodes]; rc = new int[nodes]; sm = new long[nodes];
int[] root = new int[q + 2];
root[0] = build(1, n);
int versions = 1;
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
in.nextToken(); int t = (int) in.nval; in.nextToken(); int v = (int) in.nval;
in.nextToken(); int x1 = (int) in.nval; in.nextToken(); long x2 = (long) in.nval;
if (t == 1) root[versions++] = update(root[v], 1, n, x1, x2);
else sb.append(query(root[v], 1, n, x1, (int) x2)).append('\n');
}
System.out.print(sb);
}
}
66
151
39
108
40
23
Python
import sys
sys.setrecursionlimit(10000)
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:n + 2]]
lc, rc, sm = [0], [0], [0] # node 0 is unused
def new(l, r, s):
lc.append(l); rc.append(r); sm.append(s)
return len(sm) - 1
def build(lo, hi):
if lo == hi: return new(0, 0, a[lo])
mid = (lo + hi) // 2
l, r = build(lo, mid), build(mid + 1, hi)
return new(l, r, sm[l] + sm[r])
def update(old, lo, hi, i, x): # returns a NEW node
if lo == hi: return new(0, 0, x)
mid = (lo + hi) // 2
if i <= mid: l, r = update(lc[old], lo, mid, i, x), rc[old]
else: l, r = lc[old], update(rc[old], mid + 1, hi, i, x)
return new(l, r, sm[l] + sm[r])
def query(t, lo, hi, l, r):
if r < lo or hi < l: return 0
if l <= lo and hi <= r: return sm[t]
mid = (lo + hi) // 2
return query(lc[t], lo, mid, l, r) + query(rc[t], mid + 1, hi, l, r)
root = [build(1, n)]
out, p = [], n + 2
for _ in range(q):
t, v, x, y = (int(z) for z in data[p:p + 4]); p += 4
if t == 1: root.append(update(root[v], 1, n, x, y))
else: out.append(query(root[v], 1, n, x, y))
print("\n".join(map(str, out)))
main()
66
151
39
108
40
23
Problem V2 · Exam Ranks
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200001, NODES = 20 * N; // node 0 = the empty tree
int n, q, m, tot, a[N], vals[N], lc[NODES], rc[NODES], cnt[NODES], root[N];
int insert(int old, int lo, int hi, int p) { // one more mark with rank p
int t = ++tot;
lc[t] = lc[old], rc[t] = rc[old], cnt[t] = cnt[old] + 1;
if (lo == hi) return t;
int mid = (lo + hi) / 2;
if (p <= mid) lc[t] = insert(lc[old], lo, mid, p);
else rc[t] = insert(rc[old], mid + 1, hi, p);
return t;
}
int kth(int u, int v, int lo, int hi, int k) { // tree v minus tree u
if (lo == hi) return lo;
int mid = (lo + hi) / 2, left = cnt[lc[v]] - cnt[lc[u]];
if (k <= left) return kth(lc[u], lc[v], lo, mid, k);
return kth(rc[u], rc[v], mid + 1, hi, k - left);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) vals[i - 1] = a[i];
sort(vals, vals + n);
m = unique(vals, vals + n) - vals; // coordinate compression
for (int i = 1; i <= n; i++)
root[i] = insert(root[i - 1], 1, m, lower_bound(vals, vals + m, a[i]) - vals + 1);
while (q--) {
int l, r, k;
cin >> l >> r >> k;
cout << vals[kth(root[l - 1], root[r], 1, m, k) - 1] << "\n";
}
}
61
40
90
40
Java (kth walks iteratively)
import java.util.*;
import java.io.*;
public class Main {
static int tot = 0;
static int[] lc, rc, cnt; // node 0 = the empty tree
static int insert(int old, int lo, int hi, int p) {
int t = ++tot;
lc[t] = lc[old]; rc[t] = rc[old]; cnt[t] = cnt[old] + 1;
if (lo == hi) return t;
int mid = (lo + hi) / 2;
if (p <= mid) lc[t] = insert(lc[old], lo, mid, p);
else rc[t] = insert(rc[old], mid + 1, hi, p);
return t;
}
static int kth(int u, int v, int lo, int hi, int k) { // tree v minus tree u
while (lo < hi) {
int mid = (lo + hi) / 2, left = cnt[lc[v]] - cnt[lc[u]];
if (k <= left) { u = lc[u]; v = lc[v]; hi = mid; }
else { k -= left; u = rc[u]; v = rc[v]; lo = mid + 1; }
}
return lo;
}
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedInputStream(System.in));
in.nextToken(); int n = (int) in.nval; in.nextToken(); int q = (int) in.nval;
int[] a = new int[n + 1];
for (int i = 1; i <= n; i++) { in.nextToken(); a[i] = (int) in.nval; }
int[] vals = Arrays.copyOfRange(a, 1, n + 1);
Arrays.sort(vals);
int m = 0;
for (int i = 0; i < n; i++) if (i == 0 || vals[i] != vals[i - 1]) vals[m++] = vals[i]; // compress
lc = new int[20 * (n + 1)]; rc = new int[20 * (n + 1)]; cnt = new int[20 * (n + 1)];
int[] root = new int[n + 1];
for (int i = 1; i <= n; i++) root[i] = insert(root[i - 1], 1, m, Arrays.binarySearch(vals, 0, m, a[i]) + 1);
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
in.nextToken(); int l = (int) in.nval; in.nextToken(); int r = (int) in.nval; in.nextToken(); int k = (int) in.nval;
sb.append(vals[kth(root[l - 1], root[r], 1, m, k) - 1]).append('\n');
}
System.out.print(sb);
}
}
61
40
90
40
Python (iterative insert and walk)
import sys
from bisect import bisect_left
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:n + 2]]
vals = sorted(set(a[1:])) # coordinate compression
m = len(vals)
lc, rc, cnt = [0], [0], [0] # node 0 = the empty tree
def insert(old, lo, hi, p):
path = [] # walk down iteratively, then create nodes bottom-up
while lo < hi:
mid = (lo + hi) // 2
if p <= mid: path.append((old, 0)); old, hi = lc[old], mid
else: path.append((old, 1)); old, lo = rc[old], mid + 1
lc.append(0); rc.append(0); cnt.append(cnt[old] + 1); t = len(cnt) - 1
for node, side in reversed(path):
l, r = (t, rc[node]) if side == 0 else (lc[node], t)
lc.append(l); rc.append(r); cnt.append(cnt[node] + 1); t = len(cnt) - 1
return t
root = [0]
for i in range(1, n + 1):
root.append(insert(root[-1], 1, m, bisect_left(vals, a[i]) + 1))
out, p = [], n + 2
for _ in range(q):
l, r, k = int(data[p]), int(data[p + 1]), int(data[p + 2]); p += 3
u, v, lo, hi = root[l - 1], root[r], 1, m
while lo < hi:
mid = (lo + hi) // 2
left = cnt[lc[v]] - cnt[lc[u]]
if k <= left: u, v, hi = lc[u], lc[v], mid
else: k -= left; u, v, lo = rc[u], rc[v], mid + 1
out.append(vals[lo - 1])
print("\n".join(map(str, out)))
main()
61
40
90
40
(Python is too slow for the full limits here; it is for understanding.)