这几天我们市赛被其他选手吊起来打orz，在这之前自己学习了一下主席树，真的不长啊（40行以内），这篇文章我们就一同走进神奇的主席树吧|´・ω・)ノ

什么是主席树呢

传统意义上的主席树就是可持久化线段树，什么叫可持久化呢？就是这棵树啊，很持久(划掉)可以记录每一次修改的内容，换句话说，就是可以访问这棵树的历史记录。是不是很厉害呢？

那么这种数据结构为什么要叫主席树呢？相传，发明主席树的人叫黄嘉泰（简称HJT，所以为什么叫主席树就一目了然了）(ó﹏ò｡)

主席树是怎么实现的呢

首先由于主席树是一颗可持久化线段树，所以他本质上是一棵线段树（这不是废话吗），所以我们先画一棵可爱的线段树。

然后我们对其中一个无辜的叶子节点进行修改，正常来说如果我们要存储之前没修改的历史版本，我们就可以再对修改过点的新线段树再新建一个新线段树，这样我们就一共有两棵完整的线段树了，就像下面一样。

但通过肉眼的观察我们发现，只有红色部分，也就是从被修改的叶子节点到根节点的一条链被修改了。所以我们就想能不能两棵线段树共用没有修改的节点呢？

当然可以啊，这样我们就只要在新的线段树上新建一条链，然后没有修改的子节点就直接指向之前的那棵线段树，这样就可以在只增加一条链的空间复杂度和时间复杂度的代价下存储下了新的那棵历史版本的线段树。

代码实现

这里我们以POJ的题目为例子。

【POJ 2104 K-th Number】
Description：
You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.
That is, given an array a[1...n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a[i...j] segment, if this segment was sorted?"
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.
Input：
The first line of the input file contains n --- the size of the array, and m --- the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000).
The second line contains n different integer numbers not exceeding 109 by their absolute values --- the array for which the answers should be given.
The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).
Output：
For each question output the answer to it --- the k-th number in sorted a[i...j] segment.
Sample Input：
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
Sample Output：
5
6
3
Hint：
This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed.

好吧我也看不懂，下面给出中文大意：
就是很简单的给出一个长为n的序列a，然后给出m个询问，每次给出三个数x,y,k，然后需要我们求出在序列a的区间【x，y】中，第k大的数是哪个。

一看到第k大数，我们蒟蒻的第一反应就是权值线段树（有更加高级算法的大佬轻喷）。如果题目求的是整个区间的第k大数，确实可以直接用裸的权值线段树【若排序后第一个数到第x个数一共有k个数，那么这个x就是第k大数】。

但是这道题需要我们求解的是区间【x，y】中的第k大数，这时我们就想，能不能对于任意【1，i】都开一棵权值线段树呢？没错，这就是正解——主席树。我们只要对于每个点i都开一棵只有一条链的不完整线段树，剩下的未修改的节点，就直接指向第i-1个节点那些子节点就可以了。

思路已经很清晰了，下面我们就一步一步来完成这个算法。

首先我们发现序列a中的数很大，直接开权值线段树肯定爆炸，所以我们需要离散化，下面给出vector离散化的模板：

int getid(int x){return(lower_bound(v.begin(),v.end(),x)-v.begin()+1);}//求出原来的数字在离散化以后的数字
for(int i=1;i<=n;i++)scanf("%d",&a[i]),v.push_back(a[i]);//读取序列a【i】
sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end());//对序列进行离散

接下来我们就只要对每个点建一棵线段树，然后我们知道权值线段树是具有可加可减性的，所以在查询【x，y】区间的时候，只要将第y棵权值线段树（【1，y】）减去第x-1棵权值线段树（【1，x-1】），得到的就是【x，y】的权值线段树。

所以基本的主程序就呼之欲出了:

for(int i=1;i<=n;i++)update(1,n,root[i],root[i-1],getid(a[i]));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&k);
        printf("%d\n",v[query(1,n,root[x-1],root[y],k)-1]);
    }
    return 0; 

剩下的问题就是，怎么样完成构建的update操作和查询的query操作了;

首先是update操作：

void update(int l,int r,int &x,int y,int pos)
{
    T[++cnt]=T[y],T[cnt].sum++,x=cnt;
    int mid=(l+r)/2;
    if(l==r)return;
    if(pos<=mid)update(l,mid,T[x].l,T[y].l,pos);
    else update(mid+1,r,T[x].r,T[y].r,pos);
}

l，r是区间的范围，x，y是线段树节点在T数组里的位置，pos为要加入的权值。接下来就很显然了，我们先新建一个空间，刚开始时左右儿子都和前一棵线段树一样，然后我们就判断要增加的权值在左半部分还是右半部分，然后就逐层修改所需增加的权值就可以了。

然后是query操作：

int query(int l,int r,int x,int y,int k)
{
    if(l==r)return(l);
    int sum=T[T[y].l].sum-T[T[x].l].sum;//求出【l，r】的权值线段树。
    int mid=(l+r)/2;
    if(k<=sum)return(query(l,mid,T[x].l,T[y].l,k));
    else return(query(mid+1,r,T[x].r,T[y].r,k-sum));
}

相似的，我们只需要像修改步骤一样，逐层找到权值线段树中的第k个节点是谁，就可以求出第k大数了。

所以总的程序就很短小：

#include<cmath>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int Maxx=1e5+6;
int n,m,cnt,a[Maxx],root[Maxx],x,y,k;
struct node{int l,r,sum;}T[Maxx*40];
vector<int>v;
int getid(int x){return(lower_bound(v.begin(),v.end(),x)-v.begin()+1);}//
void update(int l,int r,int &x,int y,int pos)
{
    T[++cnt]=T[y],T[cnt].sum++,x=cnt;
    int mid=(l+r)/2;
    if(l==r)return;
    if(pos<=mid)update(l,mid,T[x].l,T[y].l,pos);
    else update(mid+1,r,T[x].r,T[y].r,pos);
}
int query(int l,int r,int x,int y,int k)
{
    if(l==r)return(l);
    int sum=T[T[y].l].sum-T[T[x].l].sum;
    int mid=(l+r)/2;
    if(k<=sum)return(query(l,mid,T[x].l,T[y].l,k));
    else return(query(mid+1,r,T[x].r,T[y].r,k-sum));
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),v.push_back(a[i]);
    sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=1;i<=n;i++)update(1,n,root[i],root[i-1],getid(a[i]));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&k);
        printf("%d\n",v[query(1,n,root[x-1],root[y],k)-1]);
    }
    return 0; 
}

结语

主席树，这种神奇的算法，在上一题中也跑出了不俗的速度，希望你也能早日学会这种神奇的算法！希望你喜欢这篇博客！！！