可持久化线段树（主席树）新手向教程

嗯今天来讲讲一个高端玩意，叫可持久化线段树。

新手向，有点耐心是一定可以懂的

知识储备

首先你得知道线段树是什么，不然也不需要学这个东西
线段树

引入

现在呢我们来思考一个问题，如果题目有需要保存线段树更改前的各个历史版本（比如给一个数列的前n项各建一棵线段树），我们应该怎么存？
每个版本存一棵树吗？
不不不太多了会爆空间的QAQ

事实上，如果要存储前我们只需要修改少量点就可以，因为每两个版本间有很多的重复部分。

解析

圈里面是这个区间包含的数字在数列里出现的次数。
比如：现在我们有数列 2 1 3 4
黑色为只存储前1个数的线段树
现在我们要储存前两个数，完全不必完全新一棵树，可以利用原来树上和现在要建的新树一样的部分，也就是如果原来树上的某段区间在新树中仍将保持不变，那我们就把这个点（包括它的整个子树）连到新的根节点下面，从而避免了新建这些部分所用的空间和时间。

拿上面的图来说，因为数列1，2总共有两个元素而不是原来黑色树的一个，所以新建一个节点（最上面的红色那个）
然后我们发现右子树（3~4）在新树中和原来的一样，所以不做修改，直接把右子树连到新的根节点上面
再看左子树，发现发生了变化，所以创建新点，
然后以此类推，就可以得到新的线段树（红色）
p.s. 红色是前两个元素（2，1）的树

嗯大家可以自己画个图模拟一下啊

代码实现

接下来考虑如何写代码
首先我们需要建一棵各个值均为0的“空树”，这里注意一下，我们不得不使用指针，而不是像原来那样ls = pos << 1,rs = pos << 1 | 1了，因为不同的历史版本中同一个位置的点可能会有不同的编号。

对于每次新建版本，从上次建出的树根开始递归，原来的和要新建的一样就不管了，不一样就新建节点。

Code

//by floatiy

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

const int MAXN = 200000 + 5;
int n,m;
int cnt,q;
int a[MAXN],b[MAXN],head[MAXN];

struct Tree{
    int sum;
    int ls,rs;
}t[MAXN << 5];

void update(int pos){
    t[pos].sum = t[t[pos].ls].sum + t[t[pos].rs].sum;
    return;
}

int build(int L,int R){
    int pos = ++cnt;
    int mid = (L + R) >> 1;
    t[pos].sum = 0;
    if(L < R){
        t[pos].ls = build(L,mid);
        t[pos].rs = build(mid + 1,R);
    }
    return pos;
}

int modify(int L,int R,int pre,int v){
//  cout<<"DEBUG modify"<<endl;
    int pos = ++cnt;
    t[pos].ls = t[pre].ls;
    t[pos].rs = t[pre].rs;
    t[pos].sum = t[pre].sum + 1;
    if(L < R){
        int mid = (L + R) >> 1;
        if(v <= mid) t[pos].ls = modify(L,mid,t[pre].ls,v);
        else t[pos].rs = modify(mid + 1,R,t[pre].rs,v);
    }
//  update(pos);
    return pos;
}

int query(int L,int R,int ll,int rr,int k){
    if(L >= R) return L;
    int mid = (L + R) >> 1;
    int x = t[t[rr].ls].sum - t[t[ll].ls].sum;
    if(x >= k) return query(L,mid,t[ll].ls,t[rr].ls,k);
    else return query(mid + 1,R,t[ll].rs,t[rr].rs,k - x);
}

int main(){
    cin>>n>>q;
    for(int i = 1;i <= n;i++){
        scanf("%d",&a[i]);
        b[i] = a[i];
    }
    sort(b + 1,b + 1 + n);
    m = unique(b + 1,b + 1 + n) - b - 1;
    head[0] = build(1,m);
    for(int i = 1;i <= n;i++){
        int x = lower_bound(b + 1,b + 1 + m,a[i]) - b;
        head[i] = modify(1,m,head[i - 1],x);
    }
//  for(int i = 1;i <= cnt;i++){
//      cout<<"DEBUG: "<<i<<":   "<<head[i]<<" "<<t[i].ls<<" "<<t[i].rs<<" "<<t[i].sum<<endl;
//  }
    while(q--){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        int ans = query(1,m,head[x - 1],head[y],z);
        printf("%d
",b[ans]);
    }
    return 0;
}

某某杂

据说是主席在不会写分块的情况下发明的替代品