定義：主席樹是一種可持久化的線段樹 又叫函數式線段樹

剛開始學是不是覺得很蒙逼啊 其實我也是 

主席樹說簡單了 就是保留你每一步操作完成之后的線段樹 然后有可加減性

呃 。。。 這么說好像還是有點生澀

那么就拿poj2104來舉例子吧 慢慢講我覺得會很好的

題意就是給你一個100000長度的數字 然后100000次詢問［L，R］之間第k大的數字是多少

這個很容易看出來 暴力根本不可以 黑你分分鐘的事情啊 

我們怎么辦呢 想想線段樹能不能做 想來想去 一顆線段樹好像不能這么做 GG

那么我們做一個美好的假設：

我們建立100000棵美麗的線段樹 每一個線段樹的節點 表示這一個區間內有多少個數字

第一棵線段樹保存著把第一個數字插入進去之后 每個區間有多少個數字

第二棵線段樹保存著把第一個 第二個數字插入進去之后 每個區間有多少個數字

。

。

。

。

第n棵線段樹保存著把第1，2，3。。。。n個數字插入進去之后 每個區間有多少個數字

好了 我們已經建立了這么多的線段樹 我們接下來該怎么辦呢？

對 就是查詢 

可是如何查詢呢？ 假設我們要查詢［l，r］內的第k大

我們可以拿出第l－1 ，r 棵線段樹，然后兩者相減 我們想一下 這樣不就得到了相當于插入了第l到r個點所建立的一棵線段樹 這棵線段樹每個節點保留的信息是：這個區間內數字的個數 然后我們往下二分查找 就可以得到第k大了

現在的問題時 這么龐大的空間開銷我們耗費不起 我們該如何建立這樣的線段樹呢？

答案就是 我們要盡量利用重復節點 

我們可以想一下 我們每次建立線段樹 相對于前一棵線段樹 我們只修改了它的一條路徑 最多只有logn的變化 那么我們就存下這logn的變化 盡可能的利用重復節點 就可以達到重復使用的目的 有張圖你們自己體會一下 我也是盜圖 侵刪～

每次只修改一條路徑

這樣就能完成我們的主席樹了 

接下來是我自己寫的該題代碼 

#include <iostream>#include <algorithm>#include <stdio.h>#include <string.h>#include <stdlib.h>using namespace std;#define maxn (int)(1e6+10)struct node{    int cnt,l,r;}treenode[30*maxn];//定義一個結構體吧 要不心累 l 和 r 表示 左右兩個節點的序號 這個不是單純的單個線段樹了 這個還是有必要的 最好開20-40倍int tree_cnt[maxn];//每個線段樹跟節點的坐標 這個是搜索的起點啊int init[maxn];//int cop[maxn];int n,t_cnt=0,newn;//t_cnt是現在數組開到多大了 然后建立下一個的時候注意++t_cnt;int getid(int x) {return (int)(lower_bound(init,init+newn,x)-init);}//數據太大 需要離散化int insert(int num,int becopyed,int l,int r)//記住返回自己的坐標{    ++t_cnt;    treenode[t_cnt].cnt=treenode[becopyed].cnt+1;    int save=t_cnt;    int mid=(l+r)/2;    if(l==r)    {        return save;    }    else if(num<=mid)    {        treenode[save].l=insert(num,treenode[becopyed].l,l,mid);        treenode[save].r=treenode[becopyed].r;    }    else    {        treenode[save].r=insert(num,treenode[becopyed].r,mid+1,r);        treenode[save].l=treenode[becopyed].l;    }    return save;}int query(int x,int y,int k,int l,int r){    if(l==r) return l;    int p=(treenode[treenode[y].l].cnt-treenode[treenode[x].l].cnt);    int mid=(l+r)/2;    if(k<=p)    {        return query(treenode[x].l,treenode[y].l,k,l,mid);    }    else return query(treenode[x].r,treenode[y].r,k-p,mid+1,r);}//一邊做減法 一邊查詢void PRint(int x,int l,int r){    cout<<treenode[x].cnt<<' ';    if(l==r) {return;}    int mid=(l+r)>>1;    print(treenode[x].l,l,mid);    print(treenode[x].r,mid+1,r);}int main(){    int n,qnum;    cin>>n>>qnum;    for(int i=0;i<n;++i) {scanf("%d",init+i);cop[i]=init[i];}    sort(init,init+n);    newn=unique(init,init+n)-init;    for(int i=1;i<=n;++i)    {        int p=insert(getid(cop[i-1]),tree_cnt[i-1],0,n);        tree_cnt[i]=p;        //cout<<p<<endl;    }    for(int i=0;i<qnum;++i)    {        int x,y,k;        scanf("%d %d %d",&x,&y,&k);        //cin>>x>>y>>k;        int ans=query(tree_cnt[x-1],tree_cnt[y],k,0,n);        //cout<<ans<<endl;        printf("%d/n",init[ans]);        //cout<<init[ans]<<endl;    }    //cout<<endl;    //for(int i=0;i<=n;++i) print(tree_cnt[i],0,n),cout<<endl;    return 0;}