Core Concept

Persistent Segmant Trees, also known as Persistant (Value Domain) Segment Trees, maintain multiple versions of segment trees while supporting historical queries.

Time complexity: O(log n)
Total space complexity: O(m log n + 4n)

These trees preserve all historical versions while supporting standard segment tree operations and queries across any previous version.

Key Implementation Strategy

Dynamic node allocation avoids the O(4nm) complexity of brute-force tree copying. Since only the path from root to modified leaf nodes differs between consecutive versions, we only duplicate this path, achieving O(log n) complexity per update.

Practical Applications

Static Range K-th Smallest Element

Use persistent trees to maintain prefix sums [1, i] for value domain counts. Tree structures remain consistent (with shared nodes), allowing subtraction between trees at positions k_r and k_{l-1} to isolate [l, r] contributions. Perform binary search on the resulting segment tree after discretization.

Dynamic Inverse Pairs with Updates

Combine persistent trees with Fenwick tree approach. Modify trees at positions p, p + lowbit(p), etc., maintaining prefix sums via Fenwick structure. Calculate initial inverse pairs, then subtract contributions from deleted numbers while accounting for remaining valid pairs using persistent tree queries.

Time complexity: O(n log² n)

K-th Element on Tree Paths

Maintain persistent trees for root-to-node paths. For nodes u and v, path contribution equals:

g(u) + g(v) - g(lca(u, v)) - g(parent[lca(u, v)])

Query k-th largest element directly on the persistent tree.

Range Updates with Historical Queries

Handle interval modifications using lazy propagation with persistence. Apply permanent markers - update values and lazy flags only at completely covered nodes. During queries, accumulate lazy sums from root to current parenet nodes.

int modify_tree(int prev, int left, int right, int qleft, int qright, int delta) {
    int current = ++node_count;
    left_child[current] = left_child[prev];
    right_child[current] = right_child[prev];
    tree_sum[current] = tree_sum[prev];
    lazy[current] = lazy[prev];
    
    if (left >= qleft && right <= qright) {
        lazy[current] += delta;
        tree_sum[current] += (long long)delta * (right - left + 1);
        return current;
    }
    
    int mid = (left + right) >> 1;
    if (qleft <= mid) 
        left_child[current] = modify_tree(left_child[prev], left, mid, qleft, qright, delta);
    if (qright > mid) 
        right_child[current] = modify_tree(right_child[prev], mid + 1, right, qleft, qright, delta);
    
    tree_sum[current] = tree_sum[left_child[current]] + tree_sum[right_child[current]] + 
                       (right - left + 1) * lazy[current];
    return current;
}

long long range_query(int node, int left, int right, int qleft, int qright, long long accumulated_lazy) {
    if (left >= qleft && right <= qright) 
        return tree_sum[node] + (right - left + 1) * accumulated_lazy;
    
    int mid = (left + right) >> 1;
    long long result = 0;
    if (qleft <= mid)
        result += range_query(left_child[node], left, mid, qleft, qright, accumulated_lazy + lazy[node]);
    if (qright > mid)
        result += range_query(right_child[node], mid + 1, right, qleft, qright, accumulated_lazy + lazy[node]);
    return result;
}

Implementation Example: K-th Smallest Query

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 200005;

int node_count;
int original[MAX_N], sorted[MAX_N], mapping[MAX_N], roots[MAX_N];
int left_sub[MAX_N * 32], right_sub[MAX_N * 32], count[MAX_N * 32];

int construct_tree(int start, int end) {
    int current = ++node_count;
    if (start < end) {
        int mid = (start + end) >> 1;
        left_sub[current] = construct_tree(start, mid);
        right_sub[current] = construct_tree(mid + 1, end);
    }
    return current;
}

int insert_node(int previous, int start, int end, int position) {
    int current = ++node_count;
    left_sub[current] = left_sub[previous];
    right_sub[current] = right_sub[previous];
    count[current] = count[previous] + 1;
    
    if (start < end) {
        int mid = (start + end) >> 1;
        if (position <= mid)
            left_sub[current] = insert_node(left_sub[previous], start, mid, position);
        else
            right_sub[current] = insert_node(right_sub[previous], mid + 1, end, position);
    }
    return current;
}

int find_kth(int left_node, int right_node, int start, int end, int k) {
    if (start == end) return start;
    
    int left_count = count[left_sub[left_node]] - count[left_sub[right_node]];
    int mid = (start + end) >> 1;
    
    if (k <= left_count)
        return find_kth(left_sub[left_node], left_sub[right_node], start, mid, k);
    else
        return find_kth(right_sub[left_node], right_sub[right_node], mid + 1, end, k - left_count);
}

int main() {
    int n, queries;
    scanf("%d%d", &n, &queries);
    
    for (int i = 1; i <= n; i++) {
        scanf("%d", &original[i]);
        sorted[i] = original[i];
    }
    
    sort(sorted + 1, sorted + n + 1);
    int unique_count = unique(sorted + 1, sorted + n + 1) - sorted - 1;
    
    roots[0] = construct_tree(1, unique_count);
    
    for (int i = 1; i <= n; i++) {
        mapping[i] = lower_bound(sorted + 1, sorted + unique_count + 1, original[i]) - sorted;
        roots[i] = insert_node(roots[i - 1], 1, unique_count, mapping[i]);
    }
    
    while (queries--) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        int pos = find_kth(roots[r], roots[l - 1], 1, unique_count, k);
        printf("%d\n", sorted[pos]);
    }
    
    return 0;
}