Persistent Segment Tree
By @antinloop · Published 2025-10-02
Persistent Segment Tree
Persistent segment trees let you keep every historical version of a segment tree after updates, while sharing unchanged parts between versions. They are usually implemented with path-copying: each point update creates O(log n) new nodes along the update path; unchanged subtrees are reused. This enables queries on any past version in O(log n) time and uses O(log n) extra memory per update.
Below you'll find:
1. A clear description of the technique and complexity.
2. A simple persistent segment tree for point updates + range-sum queries (versioned array).
3. A classic application: persistent segment tree over values for answering k-th smallest in subarray queries (offline coordinate compressed).
---
Concept recap (short)
- A (non-persistent) segment tree stores aggregates (e.g., sums) for intervals.
- For persistence: instead of modifying nodes in-place for an update, create new nodes for the path from the root to the leaf you update; children not on that path are reused.
- Each version is represented by its root pointer/index (so you can have many versions).
- Complexity:
- Build:
O(n)(initial full build) orO(1)build for an implicit zero tree, thenO(log n)per update. - Update:
O(log n)time andO(log n)new nodes. - Query:
O(log n)time. - Memory:
O(n + m log n)nodes ifmupdates (assuming initial tree hadO(n)nodes).
Notes: lazy propagation with persistence is possible but more complex. Most standard uses are for point updates or point increments and queries across versions.
---
Example 1 — Versioned array (point update + range sum queries)
This is the most straightforward persistent segment tree: you have an array A initially; each update creates a new version that differs at one index, and you can query sum on any past version.
// persistent_sum.cpp
// Compile: g++ -O2 -std=c++17 persistent_sum.cpp -o persistent_sum
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node {
ll sum;
int l, r; // indices of children in pool (0 means null)
Node(ll s = 0, int L = 0, int R = 0) : sum(s), l(L), r(R) {}
};
struct PersistentSegTree {
int n;
vector<Node> pool; // node pool (1-indexed)
vector<int> roots; // root index for each version
PersistentSegTree(int n_) : n(n_) {
pool.reserve(4 * n * 20);
pool.emplace_back(); // index 0 unused
roots.push_back(build(1, n)); // version 0
}
int new_node(const Node &nd) {
pool.push_back(nd);
return (int)pool.size() - 1;
}
int build(int L, int R) {
if (L == R) {
return new_node(Node(0, 0, 0)); // initial values 0 (change if needed)
}
int mid = (L + R) >> 1;
int left = build(L, mid);
int right = build(mid+1, R);
return new_node(Node(pool[left].sum + pool[right].sum, left, right));
}
// point update: create a new version that sets position pos to value val
int update_point_set(int nodeIdx, int L, int R, int pos, ll val) {
if (L == R) {
// create a new leaf
return new_node(Node(val, 0, 0));
}
int mid = (L + R) >> 1;
int left = pool[nodeIdx].l;
int right = pool[nodeIdx].r;
int newLeft = left, newRight = right;
if (pos <= mid) newLeft = update_point_set(left, L, mid, pos, val);
else newRight = update_point_set(right, mid+1, R, pos, val);
ll s = pool[newLeft].sum + pool[newRight].sum;
return new_node(Node(s, newLeft, newRight));
}
// helper to create a new version that sets A[pos] = val
int create_version_set(int versionRootIdx, int pos, ll val) {
int newRoot = update_point_set(versionRootIdx, 1, n, pos, val);
roots.push_back(newRoot);
return (int)roots.size() - 1; // index of new version
}
// range sum query on a specific version root
ll query_sum(int nodeIdx, int L, int R, int ql, int qr) {
if (!nodeIdx || qr < L || R < ql) return 0;
if (ql <= L && R <= qr) return pool[nodeIdx].sum;
int mid = (L + R) >> 1;
return query_sum(pool[nodeIdx].l, L, mid, ql, qr)
+ query_sum(pool[nodeIdx].r, mid+1, R, ql, qr);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n = 8; // example size
PersistentSegTree pst(n);
// let's create a small demo walk-through:
// initial version 0: all zeros
// create version 1: set pos 3 = 5
int v1 = pst.create_version_set(pst.roots[0], 3, 5);
// create version 2: from v1 set pos 6 = 7
int v2 = pst.create_version_set(pst.roots[v1], 6, 7);
// create version 3: from v2 set pos 3 = 2 (changing index 3 again)
int v3 = pst.create_version_set(pst.roots[v2], 3, 2);
cout << "Sum in version 0 (1..8): " << pst.query_sum(pst.roots[0], 1, n, 1, n) << "\n"; // 0
cout << "Sum in version 1 (1..8): " << pst.query_sum(pst.roots[v1], 1, n, 1, n) << "\n"; // 5
cout << "Sum in version 2 (1..8): " << pst.query_sum(pst.roots[v2], 1, n, 1, n) << "\n"; // 12
cout << "Sum in version 3 (1..8): " << pst.query_sum(pst.roots[v3], 1, n, 1, n) << "\n"; // 9
// queries on subranges and versions:
cout << "v2 sum [3,6]: " << pst.query_sum(pst.roots[v2], 1, n, 3, 6) << "\n"; // 12 (5 + 7)
cout << "v3 sum [3,3]: " << pst.query_sum(pst.roots[v3], 1, n, 3, 3) << "\n"; // 2
return 0;
}
Notes
- In this example the initial array is all zeros. If you want to build from an initial array
A, you can changebuildto construct leaves fromA[L]instead of0. - Each
create_version_setreturns the version index; you keep theroots[]vector to reference any version.
---
Example 2 — K-th smallest in subarray (classic persistent segment tree over values)
Problem statement (typical): Given an array A[1..n], after preprocessing build n versions of a persistent segment tree where root[i] contains counts of values in A[1..i]. For a query (l, r, k) we want the k-th smallest number in A[l..r]. Use coordinate compression mapped to [1..M], and query using difference of two versions (root[r] and root[l-1]).
Key idea: each version is a frequency-count segment tree over the value domain (not index domain). The path to k-th is found comparing counts between left children of root[r] and root[l-1].
Complete C++:
// kth_smallest_persistent.cpp
// Compile: g++ -O2 -std=c++17 kth_smallest_persistent.cpp -o kth
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node {
int cnt; // count of numbers in this interval
int l, r; // children indices
Node(int c = 0, int L = 0, int R = 0) : cnt(c), l(L), r(R) {}
};
struct PersistentFreq {
int M; // number of distinct values (compressed domain)
vector<Node> pool;
vector<int> roots;
PersistentFreq(int M_) : M(M_) {
pool.reserve(4 * M * 20);
pool.emplace_back(); // index 0 unused
roots.push_back(0); // root[0] = empty tree (all zeros)
// Optionally create an explicit zero tree if you want: here we treat 0 as empty null root
}
int new_node(const Node &nd) {
pool.push_back(nd);
return (int)pool.size() - 1;
}
// increment count at position pos (value index) -> create new version
int update(int nodeIdx, int L, int R, int pos) {
if (L == R) {
return new_node(Node(pool[nodeIdx].cnt + 1, 0, 0));
}
int mid = (L + R) >> 1;
int left = pool[nodeIdx].l;
int right = pool[nodeIdx].r;
int newLeft = left, newRight = right;
if (pos <= mid) newLeft = update(left, L, mid, pos);
else newRight = update(right, mid+1, R, pos);
int s = pool[newLeft].cnt + pool[newRight].cnt;
return new_node(Node(s, newLeft, newRight));
}
// build versions from array of compressed values arr[1..n]
void build_from_array(const vector<int> &arr) {
int n = (int)arr.size() - 1;
roots[0] = new_node(Node(0, 0, 0)); // empty root
for (int i = 1; i <= n; ++i) {
int newRoot = update(roots[i-1], 1, M, arr[i]);
roots.push_back(newRoot);
}
}
// find k-th smallest in subarray [l..r] (1-based arr, roots built for prefix)
int kth(int rootR, int rootLminus1, int L, int R, int k) {
if (L == R) return L;
int mid = (L + R) >> 1;
int cntLeftR = pool[pool[rootR].l].cnt;
int cntLeftL = pool[pool[rootLminus1].l].cnt;
int cntInLeft = cntLeftR - cntLeftL;
if (k <= cntInLeft) {
return kth(pool[rootR].l, pool[rootLminus1].l, L, mid, k);
} else {
return kth(pool[rootR].r, pool[rootLminus1].r, mid+1, R, k - cntInLeft);
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Example array
vector<int> A = {0, 5, 1, 2, 4, 3, 2}; // 1-based (A[1]=5, A[2]=1, ...)
int n = (int)A.size() - 1;
// coordinate compression
vector<int> vals(A.begin()+1, A.end());
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
int M = (int)vals.size();
vector<int> comp(n+1);
for (int i = 1; i <= n; ++i) {
comp[i] = int(lower_bound(vals.begin(), vals.end(), A[i]) - vals.begin()) + 1; // 1..M
}
PersistentFreq pf(M);
pf.build_from_array(comp);
// queries (l, r, k)
vector<tuple<int,int,int>> queries = {
{1, 6, 1},
{1, 6, 3},
{2, 4, 2},
{3, 5, 1}
};
for (auto [l,r,k] : queries) {
int idx = pf.kth(pf.roots[r], pf.roots[l-1], 1, M, k); // idx is compressed index
int value = vals[idx-1]; // decompress
cout << "k=" << k << " in [" << l << "," << r << "] -> " << value << "\n";
}
return 0;
}
How it works (kth example)
roots[i]stores frequencies of values inA[1..i].- For
kth(l, r, k), we userootR = roots[r],rootLminus1 = roots[l-1]. - At each node we compare
cntLeftR - cntLeftL(how many numbers in[l..r]fall into the left child). Ifk≤ that, go left; otherwise go right and subtract that count fromk. When you reach a leaf, you get compressed index of the k-th smallest; decompress to original value.
Complexity: O(log M) per update and query, where M is number of distinct values (≤ n).
---
Practical tips and common pitfalls
- Memory: Each update creates
O(log n)nodes. If you havemupdates, allocatepoolcapacity accordingly (e.g.,reserve((initial_nodes + mlog2(n))1.1)), otherwisevectorreallocations will be slow. - Indices vs pointers: Using integer indices into a
vector<Node>is often faster than raw pointers for serialization and copying. - Initial build: You can either build an explicit initial tree (
O(n)nodes), or treat0as a null/empty node and build incrementally from an empty root. - Lazy propagation: Supporting range updates with lazy propagation in a persistent structure is tricky because lazy values would also need to be copied and propagated carefully. Most problems avoid this complexity; prefer range updates + persistence only when necessary.
- Stack depth: Recursive implementations may hit recursion limits for large
n(e.g.,n ~ 10^6). Usuallyn <= 2e5in competitive programming, recursion depth~ log nis safe. If you build initial full tree recursively andnis huge, consider iterative building or increase stack. - Use
intfor node indices andlong longfor sums when needed. - Coordinate compression is required for value-based persistent trees (k-th smallest) when values are large or negative.
---
Short checklist to implement from scratch
1. Decide: version by index or by operation? (keep roots[])
2. Choose node layout: {value,sum,cnt, left, right}. Use indices to pool.
3. Implement new_node to append to pool and return its index.
4. Implement initial build (either full build or empty root).
5. Implement update which clones only nodes along the path and returns new root index.
6. Implement query that walks the chosen version root(s).
7. Test thoroughly: small arrays, multiple versions, querying old versions.