Dynamic (Sparse) & Persistent Segment Trees: K-th Smallest in Subarray in O(log N)

1. Dynamic (Sparse) Segment Trees vs Persistent Segment Trees

Both structures abandon the fixed $4N$ array layout in favor of an arena pool of nodes (leftChild, rightChild, sum):

• Dynamic (Sparse) Segment Tree: Used when the coordinate range $[0, U]$ is up to $10^{18}$ and online queries forbid offline coordinate compression. Unvisited children stay 0 (the null sentinel with sum 0).
• Persistent Segment Tree (Prefix Histogram / Wavelet Isomorphism): After coordinate-compressing $A[1..N]$ into ranks $[0, M-1]$ ($M \le N$), version $R_i = \text{update}(R_{i-1}, 0, M-1, \text{rank}(A[i]), +1)$ creates $\lceil \log_2 M \rceil + 1$ new nodes. Across all $N$ insertions, total memory is $O(N \log N)$ nodes—never $O(N^2)$!

2. Production Implementation: Persistent Segment Tree for $O(\log N)$ Range $k$-th Smallest

/**
 * Persistent Segment Tree (Chairman Tree) using a Flat TypedArray Arena Pool
 * Answers: k-th smallest element (1-indexed k) in subarray A[l..r] (0-indexed) in O(log N) time.
 */
class PersistentKthSegmentTree {
  constructor(arr) {
    this.n = arr.length;
    // 1. Coordinate compress values in A
    this.sortedVals = Array.from(new Set(arr)).sort((a, b) => a - b);
    this.m = this.sortedVals.length;

    const maxNodes = (this.n + 1) * (Math.ceil(Math.log2(Math.max(2, this.m))) + 3);
    this.lc = new Int32Array(maxNodes);
    this.rc = new Int32Array(maxNodes);
    this.cnt = new Int32Array(maxNodes);
    this.ptr = 1; // Node 0 is the implicit zero sentinel (lc[0]=0, rc[0]=0, cnt[0]=0)

    this.roots = new Int32Array(this.n + 1);
    this.roots[0] = 0;

    for (let i = 0; i < this.n; i++) {
      const rank = this._lowerBound(this.sortedVals, arr[i]);
      this.roots[i + 1] = this._insert(this.roots[i], 0, this.m - 1, rank);
    }
  }

  _lowerBound(sorted, x) {
    let lo = 0, hi = sorted.length - 1;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (sorted[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }

  _insert(prevNode, vl, vr, targetRank) {
    const curr = this.ptr++;
    this.lc[curr] = this.lc[prevNode];
    this.rc[curr] = this.rc[prevNode];
    this.cnt[curr] = this.cnt[prevNode] + 1;

    if (vl === vr) return curr;
    const vm = (vl + vr) >> 1;
    if (targetRank <= vm) {
      this.lc[curr] = this._insert(this.lc[prevNode], vl, vm, targetRank);
    } else {
      this.rc[curr] = this._insert(this.rc[prevNode], vm + 1, vr, targetRank);
    }
    return curr;
  }

  /**
   * Returns the k-th smallest value (1 <= k <= r - l + 1) in A[l..r] (0-indexed)
   */
  kthSmallest(l, r, k) {
    let uPrev = this.roots[l];
    let uCurr = this.roots[r + 1];
    let vl = 0, vr = this.m - 1;

    while (vl < vr) {
      const vm = (vl + vr) >> 1;
      const leftCount = this.cnt[this.lc[uCurr]] - this.cnt[this.lc[uPrev]];
      if (k <= leftCount) {
        uPrev = this.lc[uPrev];
        uCurr = this.lc[uCurr];
        vr = vm;
      } else {
        k -= leftCount;
        uPrev = this.rc[uPrev];
        uCurr = this.rc[uCurr];
        vl = vm + 1;
      }
    }
    return this.sortedVals[vl];
  }
}

3. Complexity Matrix