A persistent segment tree maintains a complete history of all structural modifications applied to the data structure. Unlike standard implementations that overwrite previous states, this variant preserves every version, enabling direct queries on historical configurations. The core technique relies on path copying, where only nodes along the modification trajectory are duplicated, while unchanged subtrees are shared across versions.

Foundational Concepts

Two prerequisite structures form the basis of this implementation.

Value-Range Mapping

Instead of tracking array indices, each node records the frequency of numerical values falling within a specific interval. For a range spanning $[A, B]$, the node stores how many input elements lie within that domain. This allows binary descent to locate statistical properties like the K-th element.

Dynamic Node Allocation

Traditional static trees pre-allocate $4N$ slots, calculating children via bit-shift operations ($k \ll 1$). Persistent variants explicitly store child indices. Nodes are allocated sequentially from a global pool only when required, drastically reducing memory overhead for sparse modifications.

Core Mechanism: Prefix Aggregation and Path Sharing

To support arbitrary interval queries, construct $N$ sequential trees where version $i$ represents the cumulative state of the prefix $[1, i]$. Querying $[L, R]$ utilizes prefix difference logic: subtracting the node statistics of version $L-1$ from version $R$ isolates the target range.

Naively building independent trees demands $O(N^2)$ resources. Path copying optimizes this. When inserting a new value, only the root-to-leaf path changes. The new version allocates fresh nodes along this path and attaches unchanged subtrees directly from the previous version. This reduces both time and space complexity to $O(N \log M)$, where $M$ is the compressed value domain.

Range K-th Smallest Query

By storing value frequencies across prefix versions, the K-th smallest element in $[L, R]$ is found via binary descent. At each step, compute the left-subtree element count using $\text{count}(R_{\text{left}}) - \text{count}((L-1)_{\text{left}})$. If the result meets or exceeds $K$, descend left; otherwise, subtract the count from $K$ and proceed right.

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

struct PersistentNode {
    int left_child = 0;
    int right_child = 0;
    int frequency = 0;
};

const int MAX_NODES = 4000000;
PersistentNode pool[MAX_NODES];
int allocation_ptr = 0;
std::vector<int> roots;

int build_range_tree(int low, int high) {
    int current = ++allocation_ptr;
    if (low == high) return current;
    int mid = (low + high) >> 1;
    pool[current].left_child = build_range_tree(low, mid);
    pool[current].right_child = build_range_tree(mid + 1, high);
    return current;
}

int insert_value(int previous, int low, int high, int target_idx) {
    int current = ++allocation_ptr;
    pool[current] = pool[previous];
    pool[current].frequency++;
    
    if (low == high) return current;
    int mid = (low + high) >> 1;
    if (target_idx <= mid) {
        pool[current].left_child = insert_value(pool[previous].left_child, low, mid, target_idx);
    } else {
        pool[current].right_child = insert_value(pool[previous].right_child, mid + 1, high, target_idx);
    }
    return current;
}

int query_kth(int left_root, int right_root, int low, int high, int k) {
    if (low == high) return low;
    int mid = (low + high) >> 1;
    int left_count = pool[pool[right_root].left_child].frequency - pool[pool[left_root].left_child].frequency;
    
    if (left_count >= k) {
        return query_kth(pool[left_root].left_child, pool[right_root].left_child, low, mid, k);
    }
    return query_kth(pool[left_root].right_child, pool[right_root].right_child, mid + 1, high, k - left_count);
}

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> original(n + 1);
    std::vector<int> sorted_vals;
    sorted_vals.reserve(n + 1);
    sorted_vals.push_back(0);
    
    for (int i = 1; i <= n; ++i) {
        std::cin >> original[i];
        sorted_vals.push_back(original[i]);
    }
    
    std::sort(sorted_vals.begin() + 1, sorted_vals.end());
    sorted_vals.erase(std::unique(sorted_vals.begin() + 1, sorted_vals.end()), sorted_vals.end());
    int domain_size = sorted_vals.size() - 1;
    
    roots.push_back(build_range_tree(1, domain_size));
    for (int i = 1; i <= n; ++i) {
        int compressed = std::lower_bound(sorted_vals.begin() + 1, sorted_vals.end(), original[i]) - sorted_vals.begin();
        roots.push_back(insert_value(roots[i - 1], 1, domain_size, compressed));
    }
    
    while (m--) {
        int l, r, k;
        std::cin >> l >> r >> k;
        int idx = query_kth(roots[l - 1], roots[r], 1, domain_size, k);
        std::cout << sorted_vals[idx] << "\n";
    }
    return 0;
}

Historical State Point Updates

This variant supports generating new versions after modifying single positions. Each update creates a fresh root, branching only the modified path while sharing unchanged branches. Queries simply traverse the specified version's tree to retreive the historical value.

#include <iostream>
#include <vector>

struct VersionNode {
    int left = 0;
    int right = 0;
    int value = 0;
};

const int MAX_VER = 2000005;
VersionNode nodes[MAX_VER];
int alloc_cursor = 0;
std::vector<int> version_roots;

void build_initial(int& node, int low, int high, const std::vector<int>& data) {
    node = ++alloc_cursor;
    if (low == high) {
        nodes[node].value = data[low];
        return;
    }
    int mid = (low + high) >> 1;
    build_initial(nodes[node].left, low, mid, data);
    build_initial(nodes[node].right, mid + 1, high, data);
}

void update_point(int& current, int prev, int low, int high, int pos, int new_val) {
    current = ++alloc_cursor;
    nodes[current] = nodes[prev];
    if (low == high) {
        nodes[current].value = new_val;
        return;
    }
    int mid = (low + high) >> 1;
    if (pos <= mid) update_point(nodes[current].left, nodes[prev].left, low, mid, pos, new_val);
    else update_point(nodes[current].right, nodes[prev].right, mid + 1, high, pos, new_val);
}

int query_point(int node, int low, int high, int pos) {
    if (low == high) return nodes[node].value;
    int mid = (low + high) >> 1;
    if (pos <= mid) return query_point(nodes[node].left, low, mid, pos);
    return query_point(nodes[node].right, mid + 1, high, pos);
}

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> init_data(n + 1);
    for (int i = 1; i <= n; ++i) std::cin >> init_data[i];
    
    int initial_root;
    build_initial(initial_root, 1, n, init_data);
    version_roots.push_back(initial_root);
    
    for (int i = 1; i <= m; ++i) {
        int prev_ver, op;
        std::cin >> prev_ver >> op;
        if (op == 1) {
            int pos, val;
            std::cin >> pos >> val;
            int new_root;
            update_point(new_root, version_roots[prev_ver], 1, n, pos, val);
            version_roots.push_back(new_root);
        } else {
            int pos;
            std::cin >> pos;
            version_roots.push_back(version_roots[prev_ver]);
            std::cout << query_point(version_roots[prev_ver], 1, n, pos) << "\n";
        }
    }
    return 0;
}

Categorical Frequency with Swaps

To track occurrences of specific categories (e.g., colors) across intervals, maintain a separate persistent tree per category. Each structure records positional frequencies. Swapping adjacent elements requires decrementing counts at original indices and incrementing at new indices, generating updated versions for the affected categories. Range queries aggregate frequencies within specified bounds.

#include <iostream>
#include <vector>

struct CategoryNode {
    int l = 0;
    int r = 0;
    int count = 0;
};

const int MAX_NODES = 6000005;
CategoryNode tree[MAX_NODES];
int ptr = 0;
int category_roots[100005];

void apply_increment(int& root, int low, int high, int pos, int delta) {
    if (!root) root = ++ptr;
    if (low == high) {
        tree[root].count += delta;
        return;
    }
    int mid = (low + high) >> 1;
    if (pos <= mid) apply_increment(tree[root].l, low, mid, pos, delta);
    else apply_increment(tree[root].r, mid + 1, high, pos, delta);
    tree[root].count = tree[tree[root].l].count + tree[tree[root].r].count;
}

int query_category(int root, int low, int high, int q_l, int q_r) {
    if (!root || q_l > q_r) return 0;
    if (q_l <= low && high <= q_r) return tree[root].count;
    int mid = (low + high) >> 1;
    int res = 0;
    if (q_l <= mid) res += query_category(tree[root].l, low, mid, q_l, q_r);
    if (mid < q_r) res += query_category(tree[root].r, mid + 1, high, q_l, q_r);
    return res;
}

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> arr(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> arr[i];
        apply_increment(category_roots[arr[i]], 1, n, i, 1);
    }
    
    while (m--) {
        int type;
        std::cin >> type;
        if (type == 1) {
            int l, r, cat;
            std::cin >> l >> r >> cat;
            std::cout << query_category(category_roots[cat], 1, n, l, r) << "\n";
        } else {
            int idx;
            std::cin >> idx;
            int c1 = arr[idx], c2 = arr[idx + 1];
            apply_increment(category_roots[c1], 1, n, idx, -1);
            apply_increment(category_roots[c2], 1, n, idx + 1, -1);
            apply_increment(category_roots[c1], 1, n, idx + 1, 1);
            apply_increment(category_roots[c2], 1, n, idx, 1);
            std::swap(arr[idx], arr[idx + 1]);
        }
    }
    return 0;
}

Online Distinct Element Counting

Counting unique values in $[L, R]$ offline is trivial, but online queries require persistence. The approach tracks the most recent occurrence of each value. Iterating through the array, if a value reappears, its contribution is removed from the previous index and added to the current one. Each version $i$ stores contributions only from the latest occurrences up to position $i$. Querying version $R$ for the prefix sum starting at $L$ yields the count of distinct elements whose latest occurrence falls within $[L, R]$.

#include <iostream>
#include <vector>

struct DistinctNode {
    int left = 0;
    int right = 0;
    int weight = 0;
};

const int MAX_POOL = 5000005;
DistinctNode pool[MAX_POOL];
int cursor = 0;
int version_heads[100005];

void adjust_position(int& root, int prev, int low, int high, int idx, int val) {
    root = ++cursor;
    pool[root] = pool[prev];
    pool[root].weight += val;
    if (low == high) return;
    int mid = (low + high) >> 1;
    if (idx <= mid) adjust_position(pool[root].left, pool[prev].left, low, mid, idx, val);
    else adjust_position(pool[root].right, pool[prev].right, mid + 1, high, idx, val);
}

int count_unique(int target_l, int node, int low, int high) {
    if (low == high) return pool[node].weight;
    int mid = (low + high) >> 1;
    if (target_l <= mid) {
        return count_unique(target_l, pool[node].left, low, mid) + pool[pool[node].right].weight;
    }
    return count_unique(target_l, pool[node].right, mid + 1, high);
}

int main() {
    int n, m;
    std::cin >> n;
    std::vector<int> data(n + 1);
    std::vector<int> last_seen(n + 1, 0);
    
    for (int i = 1; i <= n; ++i) {
        std::cin >> data[i];
        int val = data[i];
        if (last_seen[val] == 0) {
            adjust_position(version_heads[i], version_heads[i - 1], 1, n, i, 1);
        } else {
            int intermediate;
            adjust_position(intermediate, version_heads[i - 1], 1, n, last_seen[val], -1);
            adjust_position(version_heads[i], intermediate, 1, n, i, 1);
        }
        last_seen[val] = i;
    }
    
    std::cin >> m;
    while (m--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << count_unique(l, version_heads[r], 1, n) << "\n";
    }
    return 0;
}