Pattern Guide
Persistent Segment Tree
"Keep all historical versions. Query any past state in O(log n). Share nodes across versions."
A persistent segment tree creates a new root for each update while sharing unchanged nodes with previous versions. Each update creates O(log n) new nodes. With n updates and O(n log n) space, all historical versions are queryable. Primary use: k-th smallest in range [l,r] using segment tree on sorted values (merge sort tree / wavelet tree alternative), offline range queries requiring past states.
Problems you can solve with this pattern
4 problems · click any to start solving
// Persistent segment tree for k-th smallest in range [l, r]
// Build one version per prefix of the sorted-by-value array
class PersistentSegTree {
constructor() {
this.nodes = [{left: 0, right: 0, cnt: 0}]; // node 0 = null
this.roots = [0]; // roots[i] = root of version i
}
update(prevRoot, lo, hi, pos) {
const node = this.nodes.length;
const prev = this.nodes[prevRoot];
this.nodes.push({left: prev.left, right: prev.right, cnt: prev.cnt + 1});
if (lo === hi) return node;
const mid = (lo + hi) >> 1;
if (pos <= mid) this.nodes[node].left = this.update(prev.left, lo, mid, pos);
else this.nodes[node].right = this.update(prev.right, mid+1, hi, pos);
return node;
}
// k-th smallest in range: query between two versions
kth(vL, vR, lo, hi, k) {
if (lo === hi) return lo;
const mid = (lo + hi) >> 1;
const leftCnt = this.nodes[this.nodes[vR].left].cnt - this.nodes[this.nodes[vL].left].cnt;
if (k <= leftCnt) return this.kth(this.nodes[vL].left, this.nodes[vR].left, lo, mid, k);
return this.kth(this.nodes[vL].right, this.nodes[vR].right, mid+1, hi, k - leftCnt);
}
}
// Usage for k-th smallest in arr[l..r]:
// 1. Coordinate compress arr values to [0, n-1]
// 2. Build versions: for each i, version[i] = update(version[i-1], 0, n-1, rank[i])
// 3. Query: kth(version[l-1], version[r], 0, n-1, k)Persistent segment tree (also called "merge sort tree" or "chairman tree") maintains all historical versions. When you update a node, instead of overwriting it, you create a new node and point to it. Unchanged children are shared. Each update creates exactly O(log n) new nodes. To query a range [l, r]: use version[r] - version[l-1] (like prefix sums on the segment tree versions).
// Persistent segment tree for k-th smallest in range [l, r]
// Build one version per prefix of the sorted-by-value array
class PersistentSegTree {
constructor() {
this.nodes = [{left: 0, right: 0, cnt: 0}]; // node 0 = null
this.roots = [0]; // roots[i] = root of version i
}
update(prevRoot, lo, hi, pos) {
const node = this.nodes.length;
const prev = this.nodes[prevRoot];
this.nodes.push({left: prev.left, right: prev.right, cnt: prev.cnt + 1});
if (lo === hi) return node;
const mid = (lo + hi) >> 1;
if (pos <= mid) this.nodes[node].left = this.update(prev.left, lo, mid, pos);
else this.nodes[node].right = this.update(prev.right, mid+1, hi, pos);
return node;
}
// k-th smallest in range: query between two versions
kth(vL, vR, lo, hi, k) {
if (lo === hi) return lo;
const mid = (lo + hi) >> 1;
const leftCnt = this.nodes[this.nodes[vR].left].cnt - this.nodes[this.nodes[vL].left].cnt;
if (k <= leftCnt) return this.kth(this.nodes[vL].left, this.nodes[vR].left, lo, mid, k);
return this.kth(this.nodes[vL].right, this.nodes[vR].right, mid+1, hi, k - leftCnt);
}
}
// Usage for k-th smallest in arr[l..r]:
// 1. Coordinate compress arr values to [0, n-1]
// 2. Build versions: for each i, version[i] = update(version[i-1], 0, n-1, rank[i])
// 3. Query: kth(version[l-1], version[r], 0, n-1, k)- Space: O(n log n) total for n updates
- Each version shares O(n log n - k·log n) nodes with other versions
- Query: diff between two versions = range query on value distribution
Classic application — k-th smallest in range [l,r]:
1. Coordinate compress all values
2. Build version[i] = version[i-1] + add rank of arr[i]
3. query(version[l-1], version[r], k) = k-th smallest
vs Merge sort tree: PST uses O(n log n) space vs O(n log n) for merge sort tree; PST supports persistent queries more naturally. Wavelet tree is an alternative with O(1) space factor improvement.