在学习主席树之前一定要先学会线段树

<h1>主席树定义</h1>

主要思想：主席树是利用函数式的编程思想使得线段树支持查询历史版本，同时充分的利用不同版本之间的共同版本来减少时间和空间复杂度的数据结构。一棵线段树的节点维护的是当前节点所对应的区间信息，若每次区间不同则处理较为困难。

它最基本的运用是区间第 $ k $ 小问题。

<h1>权值线段树</h1>

传统的线段树用于维护区间，可以方便的查询区间信息，权值线段树是每个叶子结点存储了某个元素出现的次数，一条线段的总和表示区间内所有数出现次数的总和。

利用权值线段树可以求出整体第 $ k $ 小。

具体方法：先离散化一遍，从根节点开始寻找，设当前左子树大小为 $ ls $ ，如果 $ k \leq ls$ ，那么说明该区间第 $ k $ 大是左子树中的第 $ k $ 小；反正，该区间第k大是右子树所代表的区间第 $ k-ls $ 小。

时间复杂度为$ O(log_2 N) $

<h1>静态主席树</h1>

我们接下来处理对于给定的不同区间的询问，查询该区间第 $ K $ 小。

我们先转化问题：如果我们有办法快速求整个区间的最值，那么我们如何回答区间 $ [l,r] $ 的最值询问呢？

最显然易见的方法是前缀和。

发明者的原话：

对于原序列的每一个前缀[1···i]建立出一棵线段树维护值域上每个数出现的次数，则其树是可减的。

那么，我们对于每一个前缀来维护一个上文提到的「权值线段树」即可。

我们在查询区间 $ [l,r] $ 的第 $ K $ 小时，转化为求 $ [1,r] $ 中去除 $ [1,l-1] $ 的元素后的第 $ K $ 大。

因为这种建树方式建出来的树是可减的，我们在递归过程中减去 $ [1,l-1] $ 的部分即可。

但是如果对于每一个前缀都建立一棵线段树，无论是时间还是空间是不可承受的，甚至不如排序处理快。

如何优化？

我们可以发现，其实我们在建树的时候，初始化静态区间的值相当于重新构建一个线段树。重新构建的线段树与之前的线段树相比，只是更改了最多 $ log_2N $ 个点。那么我们每次插入一个新的数时，我们只需要更改那 $ log_2N $ 个结点即可。

这样我们每次新插入一个点的时间复杂度从 $ Nlog_2N $ 暴力建树优化到了 $ log_2N $ 。

空间复杂度也明显优化了。

多提一点：我目前写过的主席树都是用指针写的，一般都写内存池，因为 new 开点会 TLE 。

<h1>题目&代码</h1>

题目链接

例题一：给定一个区间，维护一个操作

• 询问区间 $ [l,r] $ 的第 $ K $ 小元素。

代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

using std::map;
using std::make_pair;

const int MAXN = 200000 + 5;

struct Node{
    int cnt; //记录以该节点为根的树的节点数
    Node lc,rc;
}root[MAXN],pool[MAXN << 5],frog = pool;
//静态开空间防止TLE

Node *New(){
    Node *ret = ++frog;
    ret->cnt = 0;
    ret->lc = ret->rc = NULL;
    return ret;
}

map<int,int> S; //离散化用
int N,M,a[MAXN],origin[MAXN];

Node insert(Node prev,int l,int r,int pos){ //prev表示未插入前的最新版本，l，r表示区间，pos表示单点修改的位置，也是要插入的值离散化后的数
    Node *v = New(); //新建一个版本上的节点
    if(prev){ //特判防止RE
        v->cnt = prev->cnt; 
        v->lc = prev->lc;
        v->rc = prev->rc;
    } //更新新版本的根节点
    if(l == r){ //找到该修改的点了
        v->cnt++; //统计点数量+1
        return v;
    }
    //如果还没有找到，进行折半查找。
    int mid = (l + r) >> 1; //折半
    if(pos <= mid) //去左子树查找
        v->lc = insert(prev ? prev->lc : NULL,l,mid,pos);
    if(pos > mid)
        v->rc = insert(prev ? prev->rc : NULL,mid + 1,r,pos);
    //注意特判NULL情况防止RE
    v->cnt++; //更新大小
    return v;
}

int query(Node lr,Node rr,int l,int r,int k){ //lr表示查询时区间左的根，rr表示查询时区间右的根，l，r表示查询区间，k表示将要查询该区间排名为k的树。
    if(l == r) return l; //由于进行了离散化，当查询到最后时，返回该点在线段树内的标号即可。
    int ls = 0; //ls记录左子树的大小
    if(rr->lc) ls = rr->lc->cnt; //统计左子树大小
    if(lr && lr->lc) ls -= lr->lc->cnt; //为了按照排名决定方向而去重
    int mid = (l + r) >> 1; //折半查找
    if(k <= ls)
        return query(lr ? lr->lc : NULL,rr ? rr->lc : NULL,l,mid,k);
    else return query(lr ? lr->rc : NULL,rr ? rr->rc : NULL,mid + 1,r,k-ls);
}

int main(){
    scanf("%d%d",&N,&M);
    S.clear();
    for(int i = 1;i <= N;i++){
        scanf("%d",a + i);
        S.insert(make_pair(a[i],0)); //初始化
    }
    int tN = 0; //离散化后的元素多少（map去重）
    for(map<int,int>::iterator it = S.begin();it != S.end();it++){
        it->second = ++tN; //map类型S中：first表示原来的数字，second表示离散化赋予它的编号
        origin[tN] = it->first; //记录离散化后的数字。
    }
    for(int i = 1;i <= N;i++)
        a[i] = S[a[i]]; //a[i]离散化完成
    for(int i = 0;i < MAXN;i++)
        root[i] = NULL; //初始化root
    for(int i = 1;i <= N;i++)
        root[i] = insert(root[i-1],1,tN,a[i]); //对于每次插入，建立一个新版本。
    while(M--){
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        printf("%dn",origin[query(root[l-1],root[r],1,tN,k)]);
        //你可以感性理解主席树的历代版本相当于一个前缀和，树是可减的。
    }
    getchar();getchar();
    return 0;
}