Persistent Segment Tree
Path-copy only the changed nodes so every update creates a new version without destroying the old one.
Persistent Segment Tree
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Persistent segment tree is the standard answer to ``keep all past versions.'' The useful mental model is not ``copy the tree.'' It is ``copy only the nodes on the updated path and share everything else.''
Problem-Driven Motivation
Many contest problems ask for queries on:
historical array versions,
every prefix version of an array,
old and new states interleaved in arbitrary order.
If we literally copy the whole segment tree per update, memory becomes \(O(nq)\). But a point update only affects \(O(\log n)\) nodes. That mismatch is exactly where persistence pays off.
Recognition Pattern
Persistent segment tree is a strong fit when:
updates are point updates or otherwise touch only one root-to-leaf path,
queries refer to old versions,
prefix versions or time snapshots are natural in the statement,
an immutable version history is more useful than undo operations.
Typical contest signals are:
``query version \(t\),''
``k-th smallest on subarray \([l,r]\)'' after building prefix versions,
``every update creates a new snapshot.''
Derivation
In an ordinary segment tree, one point update changes exactly one root-to-leaf path. Every node outside that path still has the correct aggregate.
So for a new version:
clone the nodes on the updated path,
reuse all untouched children,
return the new root pointer or index.
This is called path copying. It is the whole reason persistence is cheap here.
Worked Problem
Problem.
An array supports point assignments. After every update, keep the new version. Later queries ask for the sum on \([l,r]\) in any version.
Why naive copying fails.
Copying the full array or full segment tree after every update is too expensive in both time and memory.
How persistence fixes it.
If version \(t\) updates position \(p\):
only the nodes whose segments contain \(p\) are cloned,
all other subtrees are shared with version \(t-1\).
Why queries remain correct.
Each root identifies one immutable tree whose aggregates match exactly the updates that were applied up to that version.
More advanced pattern.
For k-th smallest on subarray \([l,r]\), build one persistent frequency tree per prefix. The difference between roots \(\texttt{root[r]}\) and \(\texttt{root[l-1]}\) behaves like the multiset of the subarray.
Implementation Reasoning
The implementation uses an index-based node pool rather than raw pointers. That makes cloning explicit:
clone(node)copies one old node into the pool,the new version root is the index returned by the top-level update,
a vector of roots stores the full version history.
The invariant is simple:
Once created, a node is never mutated again by a later version unless that version first cloned it.
That immutability is exactly what makes sharing safe.
Correctness Intuition
Every version root points to a tree where each segment aggregate was recomputed from the correct children for that version. Shared nodes correspond to untouched segments, so their aggregates remain valid. Cloned nodes cover exactly the segments whose values changed.
Complexity Analysis
one point update: \(O(\log n)\) time and \(O(\log n)\) new nodes,
one query on any version: \(O(\log n)\),
total memory after \(q\) updates: \(O(n + q \log n)\).
Common Pitfalls
Accidentally mutating a shared node instead of cloning it.
Forgetting to store every returned root.
Underestimating the node-pool size when \(q\) is large.
Using persistence when rollback or plain offline prefix processing would be simpler.
Variants and Failure Modes
Persistent frequency trees are the standard order-statistics application.
Persistent lazy propagation exists, but the implementation becomes much more fragile.
If the task needs undo rather than arbitrary access to old versions, rollback structures are often simpler.
Practice Problems
Historical point updates with range queries.
K-th smallest on subarrays using prefix versions.
Any offline query problem where every prefix snapshot must remain available.
References
Code
Contest-ready reference implementation for the idea explained above.
#include <bits/stdc++.h>
using namespace std;
struct PersistentSegmentTree {
struct Node {
int left = 0;
int right = 0;
long long sum = 0;
};
int n;
vector<Node> pool;
explicit PersistentSegmentTree(int n) : n(n), pool(1) {}
int build(const vector<long long>& a, int l, int r) {
int node = clone(0);
if (l == r) {
pool[node].sum = a[l];
return node;
}
int mid = (l + r) / 2;
pool[node].left = build(a, l, mid);
pool[node].right = build(a, mid + 1, r);
pull(node);
return node;
}
int update(int node, int l, int r, int pos, long long value) {
int cur = clone(node);
if (l == r) {
pool[cur].sum = value;
return cur;
}
int mid = (l + r) / 2;
if (pos <= mid) {
pool[cur].left = update(pool[cur].left, l, mid, pos, value);
} else {
pool[cur].right = update(pool[cur].right, mid + 1, r, pos, value);
}
pull(cur);
return cur;
}
long long query(int node, int l, int r, int ql, int qr) const {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return pool[node].sum;
int mid = (l + r) / 2;
return query(pool[node].left, l, mid, ql, qr) +
query(pool[node].right, mid + 1, r, ql, qr);
}
private:
int clone(int from) {
pool.push_back(pool[from]);
return (int)pool.size() - 1;
}
void pull(int node) {
pool[node].sum = pool[pool[node].left].sum + pool[pool[node].right].sum;
}
};
// Example application: keep every version after point assignments and answer historical range sums.
vector<long long> historical_range_sum_queries(
const vector<long long>& initial,
const vector<pair<int, long long>>& updates,
const vector<array<int, 3>>& queries // {version, left, right}
) {
int n = (int)initial.size();
PersistentSegmentTree pst(n);
vector<int> roots;
roots.reserve(updates.size() + 1);
roots.push_back(pst.build(initial, 0, n - 1));
for (const auto& update : updates) {
int pos = update.first;
long long value = update.second;
roots.push_back(pst.update(roots.back(), 0, n - 1, pos, value));
}
vector<long long> answer;
answer.reserve(queries.size());
for (const auto& query : queries) {
int version = query[0];
int ql = query[1];
int qr = query[2];
answer.push_back(pst.query(roots[version], 0, n - 1, ql, qr));
}
return answer;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.