Persistent Segment Trees
Persistence means preserving access to earlier versions after updates. A persistent segment tree stores a root for each version and shares unchanged subtrees between roots. A point update changes only a root-to-leaf path, so copying the entire tree is unnecessary: allocate new nodes along that path and reuse all other child indices. This technique supports historical array sums, branching versions, and frequency-prefix structures for range K-th queries. This lesson implements point assignment and range sums across versions, with any existing version allowed as an update's parent.
Prerequisites: Segment trees, recursion, vector reallocation behavior, immutability.
Build the idea
Versions are roots, not copies
Build version 0 normally. Each node contains a sum and indices of its left/right children. roots[v] identifies the root of version v. The invariant is that once a node belongs to a published version it never changes. Multiple versions may reference the same node, which is safe because queries are read-only.
Path copying
For U v i x, copy version v's root into a fresh node, recurse into the child containing i, and replace only that child index in the fresh node. The other child index continues pointing to the old shared subtree. At the leaf, store x; on return, recompute fresh ancestors. Exactly one node per visited level is allocated. Updating version 0 after version 1 exists creates a branch, not a modification of either version.
Worked version history
Start with version 0: [1,2,3]. U 0 2 10 creates version 1: [1,10,3]. U 0 1 7 creates version 2: [7,2,3], branching directly from version 0. Their total sums are 6,14,12. The original leaf for position 3 can be shared by all versions because no update changes it. Creating version 2 cannot overwrite version 1's sum.
Safe vector allocation
The node pool is a vector and child links are integer indices. Pushing new nodes can reallocate its underlying memory. Never keep Node& references or pointers into that vector while recursive calls might push more nodes. This program first copies the old node into a local value, appends it, recurses, then assigns through the saved numeric index. Shared nodes are never edited.
Queries and extensions
A range query starts from roots[v] and otherwise behaves exactly like an ordinary segment tree. It allocates nothing. Prefix-frequency versions can subtract counts of two roots to answer K-th queries in a subarray, but that is a different invariant from the assignment/sum program here. Persistent lazy propagation is possible but requires extra care about copying before modifying shared nodes.
C++17 implementation
This is a complete program. Compile with C++17 and enter the input described below.
#include<iostream>
#include<vector>
using namespace std;
struct Node{
long long sum=0;
int left=0,right=0;
};
struct PersistentTree{
vector<Node>t=vector<Node>(1); // Index 0 is unused.
int build(int l,int r,const vector<long long>&a){
int p=(int)t.size();
t.push_back(Node{});
if(l==r){
t[p].sum=a[l];
return p;
}
int m=l+(r-l)/2;
int left=build(l,m,a),right=build(m+1,r,a);
t[p]={t[left].sum+t[right].sum,left,right};
return p;
}
// Copy only the changed root-to-leaf path; published nodes are immutable.
int setValue(int old,int l,int r,int i,long long x){
Node copy=t[old]; // No references into t survive allocation.
int p=(int)t.size();
t.push_back(copy);
if(l==r){
t[p].sum=x;
return p;
}
int m=l+(r-l)/2;
// The untouched child remains shared with the old version.
if(i<=m){
int child=setValue(copy.left,l,m,i,x);
t[p].left=child;
}
else{
int child=setValue(copy.right,m+1,r,i,x);
t[p].right=child;
}
t[p].sum=t[t[p].left].sum+t[t[p].right].sum;
return p;
}
// Historical queries allocate nothing and never modify shared nodes.
long long sum(int p,int l,int r,int ql,int qr)const{
if(qr<l||r<ql){
return 0;
}
if(ql<=l&&r<=qr){
return t[p].sum;
}
int m=l+(r-l)/2;
return sum(t[p].left,l,m,ql,qr)+sum(t[p].right,m+1,r,ql,qr);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,q;
cin>>n>>q;
vector<long long>a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
PersistentTree st;
// Each version is just a root index; updates may branch from any version.
vector<int>roots{st.build(1,n,a)};
while(q--){
char op;
int v;
cin>>op>>v;
if(op=='U'){
int i;
long long x;
cin>>i>>x;
roots.push_back(st.setValue(roots[v],1,n,i,x));
cout<<roots.size()-1<<'\n'; // New version ID.
}
else{
int l,r;
cin>>l>>r;
cout<<st.sum(roots[v],1,n,l,r)<<'\n';
}
}
}
Complexity analysis
Initial build O(n) time/nodes. Each point assignment allocates O(log n) nodes and takes O(log n) time. Each range sum takes O(log n) time and allocates no nodes. After u updates, total storage is O(n+u log n), plus O(u) root IDs; recursion depth O(log n).
Example input and output
n q, n initial values. Version 0 exists initially. U v i x creates and prints a new sequential version ID after assigning position i in version v; S v l r prints that version’s range sum. Use valid existing versions, n≥1 and valid ranges.
Input
3 5 1 2 3 U 0 2 10 U 0 1 7 S 0 1 3 S 1 1 3 S 2 1 3
Output
1 2 6 14 12
The two updates create versions 1 and 2 from version 0. Queries show that neither update changed the original or the other branch.
Practical applications
Historical sums; branching array states; offline queries by time; prefix-frequency versions for static subarray order statistics; snapshots without complete array copies.
Check your understanding
Which nodes need copying after a point update?
Put it into practice
Add a COPY v command that creates a new version identical to v without copying tree nodes.
Show a hint
Append roots[v] to the roots vector; immutable nodes can be shared without any new tree allocations.