What is a Persistent Segment Tree and when is it necessary?
ā Interview Prompt: Explain Persistent Data Structures, persistent segment tree construction via path copying, O(log N) per version, and range Kth smallest queries.
Persistent Data Structures preserve all historical versions of a data structure after updates.
Persistent Segment Tree:
When updating a leaf in a segment tree, instead of overwriting nodes, create new nodes only along the root-to-leaf path ($O(\log N)$ new nodes per update). Each version shares unchanged subtrees with previous versions.
Use Case ā Range Kth Smallest in O(log N):
Build a persistent segment tree over sorted array values. For queries, take the difference between versions $r$ and $l - 1$ to simulate a virtual segment tree for the subarray [l, r].
Code Implementation Example
// Persistent Segment Tree node
interface PSTNode {
left: PSTNode | null;
right: PSTNode | null;
count: number;
}
function update(prev: PSTNode | null, lo: number, hi: number, idx: number): PSTNode {
const node: PSTNode = { left: prev?.left ?? null, right: prev?.right ?? null, count: (prev?.count ?? 0) + 1 };
if (lo === hi) return node;
const mid = (lo + hi) >> 1;
if (idx <= mid) node.left = update(prev?.left ?? null, lo, mid, idx);
else node.right = update(prev?.right ?? null, mid + 1, hi, idx);
return node;
}
// Query: kth smallest in [l, r] using root[r] and root[l-1]
function kthSmallest(vl: PSTNode | null, vr: PSTNode | null, lo: number, hi: number, k: number): number {
if (lo === hi) return lo;
const mid = (lo + hi) >> 1;
const leftCount = (vr?.left?.count ?? 0) - (vl?.left?.count ?? 0);
return k <= leftCount
? kthSmallest(vl?.left ?? null, vr?.left ?? null, lo, mid, k)
: kthSmallest(vl?.right ?? null, vr?.right ?? null, mid + 1, hi, k - leftCount);
}Persistent Segment Trees store O(N log N) nodes for N versions. Path copying creates O(log N) new nodes per update. Essential for offline range Kth queries.