俗话说，一切高深莫测的算法都是乱搞搞出来的 主席树，顾名思义 ，就是在线段树上乱搞。 主席树是用来解决区间问题的，比如说区间第k小···
先举一个用线段树来做的栗子：
题意：给定一个长度为n的序列，输入每一个数 a[i] 后都有一个询问，询问从第一位到第 i 位第 ki 小的数； 样例： 5 3 1 2 2 1 2 4 4 2 3
这里讲讲线段树的做法。
首先，先对数据进行离散化操作 我们要建一个空树，其中存储着每一区间中的数出现的次数。 就像这样：
在输入每一个数的时候，我们要把这个数插到树中。即所对应区间出现次数+1； 这里给出在输入第五个数之后的树，就是这个样子的：
（以第五个数据为例）现在开始查找第3小的数，我们从根节点开始查找，如果左儿子的值大于等于k，我们就往左搜，因为第k小的数肯定在左儿子对应的区间里，如果左儿子的值要小于k，我们就往右搜，因为第k小的数肯定不在左儿子对应的区间里。以此类推，直到找到第k小的数为止。
接下来我们开始真正的主席树了——
题意：给定一个长度为n的序列，有q次询问，询问从第 l 位到第 r 位第 k 小的数； 样例： 5 5 3 2 1 4 2 2 2 1 3 4 1 4 5 1 1 2 2 4 4 1 分析：这里与上个问题不同的是引入了区间这一问题，这就使得线段树无法解决问题了。
该怎么办呢？可以在线段树上乱搞啊！这便是接下来要讲的主席树做法。
让我们来梳理一下思路 我们先建一棵跟空树没什么区别的树，这棵树跟上面问题的空树是一样的，存储着每一区间中的数出现的次数。 还是这样： 建树代码如下（很简单的）
int build(int l,int r)//其实只是建一个空树 { int now=++cnt; if(l<r) { int mid=(l+r)>>1; p[now].l=build(l,mid); p[now].r=build(mid+1,r); } return now; }我们进行的是离线操作 首先，排序+去重，通过unique来快速实现。某大佬的unique详解，不懂戳这 然后再插入序列中每一个数时，通过lower_bound来找到这个数应该在的位置 某巨佬的lower_bound详解，不懂戳这 这两步的目的是离散化，方便建树。 离散化代码：
n=read(),q=read(); for(int i=1;i<=n;i++)a[i]=read(),b[i]=a[i]; sort(b+1,b+1+n); m=unique(b+1,b+1+n)-b-1;//去重 build(1,m);//建空树 for(int i=1;i<=n;i++) { int num=lower_bound(b+1,b+1+m,a[i])-b;//说白了就是按照大小顺序给该点编个号 build_new(i,num);//改链，下面马上讲 }插入一个数后，该数对应区间的值都+1， 从图上来看，这个位置影响了一条链；所以我们应该把整条链给改了，但在改链的同时要保留前面的旧树，因为这是主席树操作的需要。 改链就像这样，我们以样例第一个数来说
在这里我们建立了三个新点：10号、11号和12号，要注意图中虽然把1、2、5划掉了，但程序中并不是删掉，也没有改值。 新建成的点将拥有插入第一个数之后的值。
改链后形成了一棵新的树。
不过这棵新的树和旧树共用一部分节点。 把这些节点放在一起看根本不是一棵树，因为这就是一堆树组合起来的了。 这些树在空间上是相连的，但在关系上是独立的。我们很容易就可以发现，每一个根节点都可以在一定程度上代表一棵树，因为从每一个根节点向下遍历，得到的都是在插入该根节点后得到的新树（这个地方可以画图理解一下）。 在更改一条链的过程中，首先建一个新点，作为新树的根节点 ； 知道要插入的数的值了，就看他影响左儿子还是在右儿子。 如果影响右儿子（即该点数值在右儿子对应的区间里），就建立一个新点，作为新树上一节点的右儿子， 然后把父节点和影响不到的左儿子连接起来，我们就不用管这个点左边的东西了 ； 如果影响左儿子，一样，建一个新点表示左儿子，连右边的节点； 然后我们再用sum数组记录一下每个节点所对应区间已经插入的数的个数 ，即该点的值； 这样就建立了n棵互不相同但是空间相似度很大的树； 我们用tree数组来记录每一棵树的根节点，在某种程度上可以代表一棵树，因为从每一个根节点递归遍历下来都可以得到一棵树 ，这棵树就是在插入该树根节点后得到的新树；
代码如下：
//cnt：要插入的节点的编号 //tree[i]：第i个“线段树”根节点编号、 //p[i]: i号点的左右儿子 //sum[i]: i号点的值，即i号点对应区间中数的个数 void change(int l,int r,int now,int past,int num) void build_new(int mark,int num) { //mark：当前建树的编号 //num：该插入的数的值 tree[mark]=++cnt; sum[cnt]=sum[tree[mark-1]]+1; change(1,m,cnt,tree[mark-1],num); } void change(int l,int r,int now,int past,int num) { //l，r：左右区间 //now:新树当前节点编号 //past：上一棵树的当前节点编号, if(!p[past].l&&!p[past].r)return; int mid=(l+r)>>1; if(num>mid) //这个点属于右边，就改右边，左边不动 顺着past下来 就不用管左边了 { p[now].l=p[past].l; //直接连上原树的左儿子作为新树的左儿子 p[now].r=++cnt;//开新点，作为上一新点的右儿子 sum[p[now].r]=sum[p[past].r]+1; //别忘了点权+1 （当然是要加到新点上啦） change(mid+1,r,p[now].r,p[past].r,num); } else{//左边，一样道理 p[now].r=p[past].r; p[now].l=++cnt; sum[p[now].l]=sum[p[past].l]+1; change(l,mid,p[now].l,p[past].l,num); } }改链完成后，就可以查询了 假如说我们要查[3,5]（输入顺序）范围内的第k小 类比于线段树查总区间第k小的方法，我们要把[3,5]区间看成一个线段树 怎么看呢？总不能硬生生地建树吧 这里要用到前缀思想 比如说我们要求 [3,5] 中的第k小 我们可以用 [1,5] 的每一个节点减去 [1,2] 的每一个节点，得到的就是 [3,5] 区间所对应的线段树的值 看图易于理解（左图为 [1,2] ，右图为 [1,5]，编号略去）： 两树对位相减，得到的就是 [3,5] 区间所对应的线段树的值； 如下：
由此我们可以得出，[3,5] 对应的线段树上每一个节点的值，等于 [1,5] 对应的线段树与 [1,2] 对应的线段树相同位置上的节点值之差。 于是我们就可以用 [1,5] 对应的线段树和 [1,2] 对应的线段树来表示 [3,5] 对应的线段树了。 参照线段树求第k小值的方法，我们得到以下代码：
int search(int a,int b,int l,int r,int k) { //a，b：区间首尾两树当前节点（一定在不同数的同一个位置） //l，r：查询区间，左or右 if(l==r)return l; int lm=sum[p[b].l]-sum[p[a].l]; //两节点左儿子相减，所得的值就是所查询区间（输入顺序）内的数在对应节点数值区间的个数 int mid=(l+r)>>1; if(k<=lm)return search(p[a].l,p[b].l,l,mid,k); return search(p[a].r,p[b].r,mid+1,r,k-lm); //mid前面有lm个数都给做掉了，所以只需要在 [mid+1,r] 中找出第k-lm小的数就可以了 }到这里就已经完成所有的关键操作了。
最后给出完整代码，变量名和意义和上面讲的一样
由于线段树要开4倍空间，我们的主席树每次要更改一条链，即log(n)个节点，所以空间复杂度为4n+qlog(n)； 一般我们开1<<5倍的空间（32*n）
#include<bits/stdc++.h> using namespace std; int n,q,m,cnt,a[200005],b[200005],x,y,k; int tree[200005],sum[4000005]; struct mp{ int l,r; }p[4000005]; int read() { long long f=0,p=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-') p=-1;c=getchar();} while(c>='0'&&c<='9'){f=f*10+c-'0';c=getchar();} return p*f; } int build(int l,int r) { int now=++cnt; if(l<r) { int mid=(l+r)>>1; p[now].l=build(l,mid); p[now].r=build(mid+1,r); } return now; } void change(int l,int r,int now,int past,int num) { if(!p[past].l&&!p[past].r)return; int mid=(l+r)>>1; if(num>mid) { p[now].l=p[past].l; p[now].r=++cnt; sum[p[now].r]=sum[p[past].r]+1; change(mid+1,r,p[now].r,p[past].r,num); } else{ p[now].r=p[past].r; p[now].l=++cnt; sum[p[now].l]=sum[p[past].l]+1; change(l,mid,p[now].l,p[past].l,num); } } void build_new(int mark,int num) { tree[mark]=++cnt; sum[cnt]=sum[tree[mark-1]]+1; change(1,m,cnt,tree[mark-1],num); } int search(int a,int b,int l,int r,int k) { if(l==r)return l; int lm=sum[p[b].l]-sum[p[a].l]; int mid=(l+r)>>1; if(k<=lm)return search(p[a].l,p[b].l,l,mid,k); return search(p[a].r,p[b].r,mid+1,r,k-lm); } int main() { n=read(),q=read(); for(int i=1;i<=n;i++)a[i]=read(),b[i]=a[i]; sort(b+1,b+1+n); m=unique(b+1,b+1+n)-b-1; tree[0]=1; build(1,m); for(int i=1;i<=n;i++) { int num=lower_bound(b+1,b+1+m,a[i])-b; build_new(i,num); } for(int i=1;i<=q;i++) { x=read(),y=read(),k=read(); printf("%d\n", b[search(tree[x-1],tree[y],1,m,k)]); } }完结撒花~
