AntInLoop

Persistent Segment Tree

By @antinloop · Published 2025-10-02

Persistent Segment Tree

Persistent segment trees let you keep every historical version of a segment tree after updates, while sharing unchanged parts between versions. They are usually implemented with path-copying: each point update creates O(log n) new nodes along the update path; unchanged subtrees are reused. This enables queries on any past version in O(log n) time and uses O(log n) extra memory per update.

Below you'll find:

1. A clear description of the technique and complexity.

2. A simple persistent segment tree for point updates + range-sum queries (versioned array).

3. A classic application: persistent segment tree over values for answering k-th smallest in subarray queries (offline coordinate compressed).

---

Concept recap (short)

  • A (non-persistent) segment tree stores aggregates (e.g., sums) for intervals.
  • For persistence: instead of modifying nodes in-place for an update, create new nodes for the path from the root to the leaf you update; children not on that path are reused.
  • Each version is represented by its root pointer/index (so you can have many versions).
  • Complexity:
  • Build: O(n) (initial full build) or O(1) build for an implicit zero tree, then O(log n) per update.
  • Update: O(log n) time and O(log n) new nodes.
  • Query: O(log n) time.
  • Memory: O(n + m log n) nodes if m updates (assuming initial tree had O(n) nodes).

Notes: lazy propagation with persistence is possible but more complex. Most standard uses are for point updates or point increments and queries across versions.

---

Example 1 — Versioned array (point update + range sum queries)

This is the most straightforward persistent segment tree: you have an array A initially; each update creates a new version that differs at one index, and you can query sum on any past version.

// persistent_sum.cpp
// Compile: g++ -O2 -std=c++17 persistent_sum.cpp -o persistent_sum

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Node {
    ll sum;
    int l, r; // indices of children in pool (0 means null)
    Node(ll s = 0, int L = 0, int R = 0) : sum(s), l(L), r(R) {}
};

struct PersistentSegTree {
    int n;
    vector<Node> pool;      // node pool (1-indexed)
    vector<int> roots;      // root index for each version

    PersistentSegTree(int n_) : n(n_) {
        pool.reserve(4 * n * 20);
        pool.emplace_back(); // index 0 unused
        roots.push_back(build(1, n)); // version 0
    }

    int new_node(const Node &nd) {
        pool.push_back(nd);
        return (int)pool.size() - 1;
    }

    int build(int L, int R) {
        if (L == R) {
            return new_node(Node(0, 0, 0)); // initial values 0 (change if needed)
        }
        int mid = (L + R) >> 1;
        int left = build(L, mid);
        int right = build(mid+1, R);
        return new_node(Node(pool[left].sum + pool[right].sum, left, right));
    }

    // point update: create a new version that sets position pos to value val
    int update_point_set(int nodeIdx, int L, int R, int pos, ll val) {
        if (L == R) {
            // create a new leaf
            return new_node(Node(val, 0, 0));
        }
        int mid = (L + R) >> 1;
        int left = pool[nodeIdx].l;
        int right = pool[nodeIdx].r;

        int newLeft = left, newRight = right;
        if (pos <= mid) newLeft = update_point_set(left, L, mid, pos, val);
        else newRight = update_point_set(right, mid+1, R, pos, val);

        ll s = pool[newLeft].sum + pool[newRight].sum;
        return new_node(Node(s, newLeft, newRight));
    }

    // helper to create a new version that sets A[pos] = val
    int create_version_set(int versionRootIdx, int pos, ll val) {
        int newRoot = update_point_set(versionRootIdx, 1, n, pos, val);
        roots.push_back(newRoot);
        return (int)roots.size() - 1; // index of new version
    }

    // range sum query on a specific version root
    ll query_sum(int nodeIdx, int L, int R, int ql, int qr) {
        if (!nodeIdx || qr < L || R < ql) return 0;
        if (ql <= L && R <= qr) return pool[nodeIdx].sum;
        int mid = (L + R) >> 1;
        return query_sum(pool[nodeIdx].l, L, mid, ql, qr)
             + query_sum(pool[nodeIdx].r, mid+1, R, ql, qr);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 8; // example size
    PersistentSegTree pst(n);

    // let's create a small demo walk-through:
    // initial version 0: all zeros
    // create version 1: set pos 3 = 5
    int v1 = pst.create_version_set(pst.roots[0], 3, 5);
    // create version 2: from v1 set pos 6 = 7
    int v2 = pst.create_version_set(pst.roots[v1], 6, 7);
    // create version 3: from v2 set pos 3 = 2 (changing index 3 again)
    int v3 = pst.create_version_set(pst.roots[v2], 3, 2);

    cout << "Sum in version 0 (1..8): " << pst.query_sum(pst.roots[0], 1, n, 1, n) << "\n"; // 0
    cout << "Sum in version 1 (1..8): " << pst.query_sum(pst.roots[v1], 1, n, 1, n) << "\n"; // 5
    cout << "Sum in version 2 (1..8): " << pst.query_sum(pst.roots[v2], 1, n, 1, n) << "\n"; // 12
    cout << "Sum in version 3 (1..8): " << pst.query_sum(pst.roots[v3], 1, n, 1, n) << "\n"; // 9

    // queries on subranges and versions:
    cout << "v2 sum [3,6]: " << pst.query_sum(pst.roots[v2], 1, n, 3, 6) << "\n"; // 12 (5 + 7)
    cout << "v3 sum [3,3]: " << pst.query_sum(pst.roots[v3], 1, n, 3, 3) << "\n"; // 2

    return 0;
}

Notes

  • In this example the initial array is all zeros. If you want to build from an initial array A, you can change build to construct leaves from A[L] instead of 0.
  • Each create_version_set returns the version index; you keep the roots[] vector to reference any version.

---

Example 2 — K-th smallest in subarray (classic persistent segment tree over values)

Problem statement (typical): Given an array A[1..n], after preprocessing build n versions of a persistent segment tree where root[i] contains counts of values in A[1..i]. For a query (l, r, k) we want the k-th smallest number in A[l..r]. Use coordinate compression mapped to [1..M], and query using difference of two versions (root[r] and root[l-1]).

Key idea: each version is a frequency-count segment tree over the value domain (not index domain). The path to k-th is found comparing counts between left children of root[r] and root[l-1].

Complete C++:

// kth_smallest_persistent.cpp
// Compile: g++ -O2 -std=c++17 kth_smallest_persistent.cpp -o kth

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Node {
    int cnt; // count of numbers in this interval
    int l, r; // children indices
    Node(int c = 0, int L = 0, int R = 0) : cnt(c), l(L), r(R) {}
};

struct PersistentFreq {
    int M; // number of distinct values (compressed domain)
    vector<Node> pool;
    vector<int> roots;

    PersistentFreq(int M_) : M(M_) {
        pool.reserve(4 * M * 20);
        pool.emplace_back(); // index 0 unused
        roots.push_back(0); // root[0] = empty tree (all zeros)
        // Optionally create an explicit zero tree if you want: here we treat 0 as empty null root
    }

    int new_node(const Node &nd) {
        pool.push_back(nd);
        return (int)pool.size() - 1;
    }

    // increment count at position pos (value index) -> create new version
    int update(int nodeIdx, int L, int R, int pos) {
        if (L == R) {
            return new_node(Node(pool[nodeIdx].cnt + 1, 0, 0));
        }
        int mid = (L + R) >> 1;
        int left = pool[nodeIdx].l;
        int right = pool[nodeIdx].r;
        int newLeft = left, newRight = right;
        if (pos <= mid) newLeft = update(left, L, mid, pos);
        else newRight = update(right, mid+1, R, pos);
        int s = pool[newLeft].cnt + pool[newRight].cnt;
        return new_node(Node(s, newLeft, newRight));
    }

    // build versions from array of compressed values arr[1..n]
    void build_from_array(const vector<int> &arr) {
        int n = (int)arr.size() - 1;
        roots[0] = new_node(Node(0, 0, 0)); // empty root
        for (int i = 1; i <= n; ++i) {
            int newRoot = update(roots[i-1], 1, M, arr[i]);
            roots.push_back(newRoot);
        }
    }

    // find k-th smallest in subarray [l..r] (1-based arr, roots built for prefix)
    int kth(int rootR, int rootLminus1, int L, int R, int k) {
        if (L == R) return L;
        int mid = (L + R) >> 1;
        int cntLeftR = pool[pool[rootR].l].cnt;
        int cntLeftL = pool[pool[rootLminus1].l].cnt;
        int cntInLeft = cntLeftR - cntLeftL;
        if (k <= cntInLeft) {
            return kth(pool[rootR].l, pool[rootLminus1].l, L, mid, k);
        } else {
            return kth(pool[rootR].r, pool[rootLminus1].r, mid+1, R, k - cntInLeft);
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Example array
    vector<int> A = {0, 5, 1, 2, 4, 3, 2}; // 1-based (A[1]=5, A[2]=1, ...)
    int n = (int)A.size() - 1;

    // coordinate compression
    vector<int> vals(A.begin()+1, A.end());
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int M = (int)vals.size();

    vector<int> comp(n+1);
    for (int i = 1; i <= n; ++i) {
        comp[i] = int(lower_bound(vals.begin(), vals.end(), A[i]) - vals.begin()) + 1; // 1..M
    }

    PersistentFreq pf(M);
    pf.build_from_array(comp);

    // queries (l, r, k)
    vector<tuple<int,int,int>> queries = {
        {1, 6, 1},
        {1, 6, 3},
        {2, 4, 2},
        {3, 5, 1}
    };

    for (auto [l,r,k] : queries) {
        int idx = pf.kth(pf.roots[r], pf.roots[l-1], 1, M, k); // idx is compressed index
        int value = vals[idx-1]; // decompress
        cout << "k=" << k << " in [" << l << "," << r << "] -> " << value << "\n";
    }

    return 0;
}

How it works (kth example)

  • roots[i] stores frequencies of values in A[1..i].
  • For kth(l, r, k), we use rootR = roots[r], rootLminus1 = roots[l-1].
  • At each node we compare cntLeftR - cntLeftL (how many numbers in [l..r] fall into the left child). If k ≤ that, go left; otherwise go right and subtract that count from k. When you reach a leaf, you get compressed index of the k-th smallest; decompress to original value.

Complexity: O(log M) per update and query, where M is number of distinct values (≤ n).

---

Practical tips and common pitfalls

  • Memory: Each update creates O(log n) nodes. If you have m updates, allocate pool capacity accordingly (e.g., reserve((initial_nodes + mlog2(n))1.1)), otherwise vector reallocations will be slow.
  • Indices vs pointers: Using integer indices into a vector<Node> is often faster than raw pointers for serialization and copying.
  • Initial build: You can either build an explicit initial tree (O(n) nodes), or treat 0 as a null/empty node and build incrementally from an empty root.
  • Lazy propagation: Supporting range updates with lazy propagation in a persistent structure is tricky because lazy values would also need to be copied and propagated carefully. Most problems avoid this complexity; prefer range updates + persistence only when necessary.
  • Stack depth: Recursive implementations may hit recursion limits for large n (e.g., n ~ 10^6). Usually n <= 2e5 in competitive programming, recursion depth ~ log n is safe. If you build initial full tree recursively and n is huge, consider iterative building or increase stack.
  • Use int for node indices and long long for sums when needed.
  • Coordinate compression is required for value-based persistent trees (k-th smallest) when values are large or negative.

---

Short checklist to implement from scratch

1. Decide: version by index or by operation? (keep roots[])

2. Choose node layout: {value,sum,cnt, left, right}. Use indices to pool.

3. Implement new_node to append to pool and return its index.

4. Implement initial build (either full build or empty root).

5. Implement update which clones only nodes along the path and returns new root index.

6. Implement query that walks the chosen version root(s).

7. Test thoroughly: small arrays, multiple versions, querying old versions.