可持久化线段树

前言

本人也没有学多长时间的可持久化数据结构，所以这篇博文多少会有些浅显，还请各位海涵并对学术性错误予以指正。

因为网络的原因我无法把评论区初始化掉，反正我的博客也没人看，而且这里边很多的 Md 和 $\LaTeX$ 都会出现一些奇妙的事情，所以我不会按照之前那种严格的规范来写博文了（避免 $\LaTeX$ 出锅）。

之前出过的锅我就不修了，反正洛谷博客上几乎也有备份，想看可以过去。

Intro

”可持久化“的意思是我们在一个 DS 不断修改之后，我们可以找回每一个历史版本。

可持久化的 DS 多种多样，本文主要讲述可持久化线段树，又名主席树（也许未来还会更新？）。

请注意：搞学术的人并不认可主席树这个称呼，主席树只是 OI 选手们起的名字，所以碰上了某个计算机科学家你跟他说一句：“您知道主席树吗？”，他只会说那不是可持久化线段树吗，哪来的主席树。

实现可持久化其实有一个暴力的办法：你不是要修改 $m$ 次吗？我直接给空间开个 $m$ 倍！

出题人：好，空间不够，您 MLE 了。

寄。

这个时候我们就要充分发扬人类智慧了。

我们分析一下，如果我们改了一个节点，有很多节点是不会被修改的，也就是说，修改了一个节点，不关很多节点的事。

那么我们只需要新建一些新的节点来表示更新后且被影响到的节点就可以了。

由于主席树的特性，我们采用动态开点线段树，也便于节省空间。

开新节点的时候我们只需要让总结点个数加 1 即可，访问子节点在结构体里定义，不要用父子二倍不然寄掉，存储根可以开个数组来干。

我们扔个例题吧：

https://www.luogu.com.cn/problem/P3834

我们分析一下，我们要求出第 $k$ 小的数，那么我们可以对值域建一棵线段树，好吧值域有点大，我们给它离散化。接下来主席树上的节点要维护的就是从 1 到 $i$ 中数的个数。

可以发现一个事情，是不是类似前缀和？

没错，和前缀和非常相似！

那么我们就只需要通过将 $r$ 版本的值减去 $l$ 版本的值就可以得出这两个版本之间有多少个数。

查询第 $k$ 小，我们就只需要判断当前要查询的 $r$ 版本到 $l$ 版本之间的左儿子间的数的个数，如果个数比 $k$ 大，说明第 $k$ 小一定是在左儿子里，进入左儿子去找，否则我们将 $k$ 减去个数，然后去右儿子里边找。

当我们找到了一个叶子节点，说明我们已经找到了第 $k$ 小的数！

给 Code：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include<iostream>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

int rd() {
    int x = 0, w = 1;
    char c = getchar();

    while(c < '0' || c > '9') {
        if(c == '-') w = -1;
        c = getchar();
    }

    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }

    return x * w;
}

const int N = 1e5 + 5;

struct Tree {
    int ls, rs;
    int dat;

    #define ls(x) t[x].ls
    #define rs(x) t[x].rs
    #define dat(x) t[x].dat

}t[N << 2];

int root[N], top;
int n, m;
int a[N], b[N];

int build(int l, int r) {
    int p = ++top;
    if(l == r) return p;

    int mid = (r - l) / 2 + l;

    ls(p) = build(l, mid);
    rs(p) = build(mid + 1, r);

    return p;
}

int change(int now, int l, int r, int x) {
    int p = ++top;
    t[p] = t[now];
    if(l == r) {
        ++dat(p);
        return p;
    }

    int mid = (r - l) / 2 + l;
    if(x <= mid) ls(p) = change(ls(p), l, mid, x);
    if(x > mid) rs(p) = change(rs(p), mid + 1, r, x);
    dat(p) = dat(ls(p)) + dat(rs(p));
    return p;
}

int ask(int l, int r, int L, int R, int k) {
    // printf("%d %d %d\n",L,R,dat(rs(r)) - dat(rs(l)));
    if(L == R) return L;

    int rcnt = (dat(rs(r)) - dat(rs(l)));
    int mid = (R - L) / 2 + L;
    if(rcnt >= k) return ask(rs(l), rs(r), mid + 1, R, k);
    else return ask(ls(l), ls(r), L, mid, k - rcnt);
}

int main() {
    int T = rd();
    while(T--) {
        n = rd(), m = rd();
        memset(t, 0, sizeof(t));
        top = 0;
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(root, 0, sizeof(root));
        for(int i = 1; i <= n; ++i) a[i] = rd(), b[i] = a[i];

        sort(a + 1, a + 1 + n);
        int num = unique(a + 1, a + 1 + n) - a - 1;
        root[0] = build(1, num);
        for(int i = 1; i <= n; ++i) {
            int k = lower_bound(a + 1, a + num + 1, b[i]) - a;
            // cout<<k<<" ";
            root[i] = change(root[i - 1], 1, num, k);
        }
        // cout<<endl;
        while(m--) {
            int l = rd(), r = rd(), k = rd();
            printf("%d\n", a[ask(root[l - 1], root[r], 1, num, k)]);
        }
    }
    return 0;
}