本文主要是介绍一看就懂的主席树（不带修），逐句代码分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
俗话说，一切高深莫测的算法都是乱搞搞出来的
主席树，顾名思义 ，就是在线段树上乱搞。
主席树是用来解决区间问题的，比如说区间第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)]);}
}
完结撒花~
这篇关于一看就懂的主席树（不带修），逐句代码分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
