数据结构可持久化前提,
数据结构本身的拓扑结构在维护(基本操作)中不发生变化. 例外平衡树待补充…

数据结构可持久化应用场景,
对于数据结构的每一次更新, 储存下更新前的数据结构状态. 我们需要查询数据结构的不同更新次数的状态时, 会用到可持久化数据结构.

数据结构可持久化思想,
类似git, 记录当前版本与其前一个版本不一样的地方. 也就是新的修改必须全部创建出来.

权值线段树

维护区间[l, r]中元素个数num

讲解
https://blog.csdn.net/yanweiqi1754989931/article/details/117380913
例题
https://www.luogu.com.cn/problem/P3369
https://blog.csdn.net/weixin_45606191/article/details/114599088

/**
 *    author:  mikezheng
 *    created: 25.05.2022 15:53:43
**/
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+10;

int n, cnt, q[N], a[N], b[N], tr[N*2];

// x is the id that value is discretized
void modify(int l, int r, int u, int x, int f) {
    if (l == r) {
        if (f == 0) tr[u] -- ;
        else tr[u] ++ ;
    }
    else {
        int mid = l + r >> 1;
        if (x <= mid) modify(l, mid, u<<1, x, f);
        else modify(mid+1, r, u<<1|1, x, f);
        tr[u] = tr[u<<1] + tr[u<<1|1];
    }
}

int querykmin(int l, int r, int u, int k) {
    if (l == r) return b[l];
    int mid = l + r >> 1, lnum = tr[u<<1];
    if (k <= lnum) return querykmin(l, mid, u<<1, k);
    else return querykmin(mid+1, r, u<<1|1, k-lnum);
}

int querynum(int l, int r, int u, int x, int y) {
    if (x == l && y == r) return tr[u];
    else {
        int mid = l + r >> 1;
        if (x > mid) return querynum(mid+1, r, u<<1|1, x, y);
        else if (y <= mid) return querynum(l, mid, u<<1, x, y);
        else return querynum(l, mid, u<<1, x, mid) + querynum(mid+1, r, u<<1|1, mid+1, y);
    }
}

inline int get(int x) {
    return lower_bound(b+1, b+cnt+1, x) - b;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1 ; i <= n ; i ++ ) {
        cin >> q[i] >> a[i];
        if (q[i] == 1 || q[i] == 5 || q[i] == 6) b[++cnt] = a[i];
    }
    sort(b+1, b+cnt+1);
    cnt = unique(b+1, b+cnt+1) - b-1;
    for (int i = 1 ; i <= n ; i ++ ) {
        if (q[i] == 1) modify(1, cnt, 1, get(a[i]), 1);
        else if (q[i] == 2) modify(1, cnt, 1, get(a[i]), 0);
        else if (q[i] == 3) {
            if (get(a[i]) == 1) cout << 1 << '\n';
            else cout << querynum(1, cnt, 1, 1, get(a[i])-1)+1 << '\n';
        }
        else if (q[i] == 4) cout << querykmin(1, cnt, 1, a[i]) << '\n';
        else if (q[i] == 5) {
            if (get(a[i]) == 1) cout << a[i] << '\n';
            cout << querykmin(1, cnt, 1, querynum(1, cnt, 1, 1, get(a[i])-1)) << '\n';
        }
        else if (q[i] == 6) {
            if (get(a[i]) == cnt) cout << a[i] << '\n';
            cout << querykmin(1, cnt, 1, tr[1] - querynum(1, cnt, 1, get(a[i])+1, cnt) + 1) << '\n';
        }
    }
  return 0;
}

主席树(可持久化权值线段树)

https://www.luogu.com.cn/blog/LonecharmRiver/zhu-xi-shu

• 动态开点（邻接表开点方式，非堆存储）
• 权值线段树
• 持久化

注: 难以进行区间修改操作(当然我们可以通过永久化懒标记实现, 一般不会考)

例题

/**
 *    author:  mikezheng
 *    created: 26.05.2022 15:14:53
**/
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+10;

// tr: 存储结点（区间）的元素个数
int n, m, a[N], b[N], root[N], ls[N*2+18*N], rs[N*2+18*N], tr[N*2+18*N], cnt, idx;

void build(int &rt, int l, int r) {
    rt = ++ idx;
    if (l == r) return ;
    int mid = l + r >> 1;
    build(ls[rt], l, mid); build(rs[rt], mid+1, r);
}

int modify(int rt, int l, int r, int x) {
    int u = ++ idx;
    ls[u] = ls[rt], rs[u] = rs[rt], tr[u] = tr[rt]+1;
    if (l == r) return u;
    int mid = l + r >> 1;
    if (x <= mid) ls[u] = modify(ls[u], l, mid, x);
    else rs[u] = modify(rs[u], mid+1, r, x);
    return u;
}

int query(int rtl, int rtr, int l, int r, int k) {
    int x = tr[ls[rtr]] - tr[ls[rtl]];
    if (l == r) return l; int mid = l + r >> 1;
    if (x >= k) return query(ls[rtl], ls[rtr], l, mid, k);
    else return query(rs[rtl], rs[rtr], mid+1, r, k-x);
}

inline int get(int x) {
    return lower_bound(b+1, b+n+1, x) - b;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i ++ ) {
        cin >> a[i]; b[i] = a[i];
    }
    sort(b+1, b+n+1); 
    cnt = unique(b+1, b+n+1) - b-1;
    build(root[0], 1, cnt); // root[0]=1
    for (int i = 1 ; i <= n ; i ++ ) { // 1~n releases
        root[i] = modify(root[i-1], 1, cnt, get(a[i]));
    }
    for (int i = 1 ; i <= m ; i ++ ) {
        int l, r, k; cin >> l >> r >> k;
        // root[i]插入第i个数的版本
        cout << b[query(root[l-1], root[r], 1, cnt, k)] << '\n';
    }
  return 0;
}