Persistent Segment Tree (Path-Copying Time Travel & Range K-th Smallest)

Path Copying & Structural Sharing

A standard point update in a segment tree mutates only the $O(\log n)$ nodes along the root-to-leaf path. If instead of mutating those nodes in place we allocate a new node for each visited ancestor while pointing its unmodified child pointer to the existing subtree from the previous version, we achieve full persistence:

Time per update: $O(\log n)$
Extra space per update: $O(\log n)$ nodes
Version branching: Any historical version $v$ can be queried or forked into a new branch in $O(\log n)$ time.

Static Range $k$-th Smallest in $O(\log n)$ Time

Given an array $A[0..n-1]$, how do we find the $k$-th smallest element in any subarray $A[l..r]$ in $O(\log n)$ time?

Coordinate-compress the distinct values of $A$ into $[0..U-1]$.
Build $n$ versions of a frequency Persistent Segment Tree over value space $[0..U-1]$, where version $i+1$ inserts $A[i]$ into version $i$.
For any subarray $A[l..r]$, the frequency of values in any value bucket $[\text{lo}, \text{mid}]$ is simply: $$\text{count} = \text{root}_{r+1}.\text{left}.\text{sum} - \text{root}_l.\text{left}.\text{sum}$$
Walking $\text{root}_{r+1}$ and $\text{root}_l$ in lockstep finds the exact $k$-th smallest element in $O(\log U)$ time.

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Path-Copying Point Updates

Core Mechanical Concept: Path-Copying Point Updates
Target Module: index.js (Step1)
Engineering Specification: Implement update(version, index, newValue) by cloning only the $O(\log n)$ nodes along the root-to-leaf path and sharing the unchanged sibling pointer.
Verification Invariant: verifies Step 1: Path-Copying Point Updates

Step 2: Additive Version Branching

Core Mechanical Concept: Additive Version Branching
Target Module: index.js (Step2)
Engineering Specification: Implement add(version, index, delta) to support branching from any historical version ID.
Verification Invariant: verifies Step 2: Additive Version Branching

Step 3: Historical Range Queries

Core Mechanical Concept: Historical Range Queries
Target Module: index.js (Step3)
Engineering Specification: Implement queryRange(version, ql, qr) starting from this._roots[version].
Verification Invariant: verifies Step 3: Historical Range Queries

Step 4: Range K-th Smallest via Prefix Persistent Trees

Core Mechanical Concept: Range K-th Smallest via Prefix Persistent Trees
Target Module: index.js (Step4)
Engineering Specification: Insert elements $A[0..n-1]$ into a value-indexed Persistent Segment Tree so root[r+1] - root[l] forms a virtual frequency segment tree over subarray $A[l..r]$, enabling $O(\log U)$ quantile queries.
Verification Invariant: verifies Step 4: Range K-th Smallest via Prefix Persistent Trees

Asymptotic & Memory Layout Guarantees

Category: Range Queries & Trees
Difficulty: Advanced (~50 minutes)
Key Architectural Highlights:
• O(log n) structural path-copying creating immutable versioned roots without mutating history
• Historical range sum queries across arbitrary past versions in O(log n) time
• Wavelet-style Range K-th Smallest (Order Statistic on [L, R]) by walking two version roots simultaneously
Tags & Primitives: Persistent Segment Tree, Path Copying, Time Travel Queries, Static Range K-th Smallest, Functional Data Structures

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.

Code & Verify in the Browser Workbench