AntInLoop

Persistent Data Structures (Persistent Segment Tree)

Persistent Data Structures preserve all historical versions after every update using path copying, allowing O(log n) versioned queries and static range k-th smallest element queries.

Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code

Persistent Data Structures (Persistent Segment Tree)

A Persistent Data Structure preserves every previous version whenever it is modified! Instead of copying an entire $O(n)$ tree on an update, Path Copying only allocates the $O(\log n)$ nodes along the root-to-leaf path that actually changed, sharing all unmodified subtrees with the previous version! Building a Persistent Segment Tree over prefixes 0..i solves "find the $k$-th smallest element in A[L..R]" in $O(\log n)$ per query!

At a Glance

| Property | Value |

| :--- | :---: |

| Update Time & Space per Version | $O(\log n)$ new nodes |

| Total Space after $q$ Updates | $O(n + q \log n)$ |

| Range $k$-th Smallest Query [L, R] | $O(\log n)$ (subtract version root[L - 1] from root[R]) |

---

Practice Problems

Hard

1. Static Range $k$-th Smallest Element (SPOJ MKTHNUM)

Given an array A[0..n-1], answer queries: what is the $k$-th smallest element in A[l..r] (1-indexed k) in $O(\log n)$ time!

Approach: Coordinate-compress A to 0..m-1. Build root[i + 1] = update(root[i], rank[A[i]], +1). To query [l, r], walk root[r + 1] and root[l] in lockstep: the number of elements in the left value-half is leftCount = tree[L(r+1)].cnt - tree[L(l)].cnt! Time: $O((n + q)\log n)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <vector>

struct PNode { int l = 0, r = 0, cnt = 0; };

struct PersistentSegTree {
    int m;
    std::vector<PNode> t;
    std::vector<int> roots;

    explicit PersistentSegTree(int distinctVals) : m(distinctVals) {
        t.push_back({0, 0, 0}); // null node 0
        roots.push_back(0);
    }

    int update(int prev, int l, int r, int pos) {
        int cur = static_cast<int>(t.size());
        t.push_back(t[prev]);
        ++t[cur].cnt;
        if (l < r) {
            int mid = (l + r) / 2;
            if (pos <= mid) t[cur].l = update(t[prev].l, l, mid, pos);
            else t[cur].r = update(t[prev].r, mid + 1, r, pos);
        }
        return cur;
    }

    int kth(int u, int v, int l, int r, int k) const {
        if (l == r) return l;
        int mid = (l + r) / 2;
        int leftCnt = t[t[v].l].cnt - t[t[u].l].cnt;
        if (k <= leftCnt) return kth(t[u].l, t[v].l, l, mid, k);
        return kth(t[u].r, t[v].r, mid + 1, r, k - leftCnt);
    }
};

int main() {
    std::vector<int> a = {1, 5, 2, 6, 3, 7, 4};
    std::vector<int> vals = a;
    std::sort(vals.begin(), vals.end());
    vals.erase(std::unique(vals.begin(), vals.end()), vals.end());
    int m = static_cast<int>(vals.size());

    PersistentSegTree pst(m);
    for (int x : a) {
        int rk = static_cast<int>(std::lower_bound(vals.begin(), vals.end(), x) - vals.begin());
        pst.roots.push_back(pst.update(pst.roots.back(), 0, m - 1, rk));
    }

    // 3rd smallest in a[1..4] = {5, 2, 6, 3} -> sorted {2, 3, 5, 6} -> 5
    int rkAns = pst.kth(pst.roots[1], pst.roots[5], 0, m - 1, 3);
    std::cout << vals[rkAns] << "\n"; // 5
    return 0;
}

</details>

---

Related Structures & Algorithms

  • Segment Tree — mutable base structure of a Persistent Segment Tree.