定義：主席樹(shù)是一種可持久化的線(xiàn)段樹(shù) 又叫函數(shù)式線(xiàn)段樹(shù)

剛開(kāi)始學(xué)是不是覺(jué)得很蒙逼啊 其實(shí)我也是 

主席樹(shù)說(shuō)簡(jiǎn)單了 就是保留你每一步操作完成之后的線(xiàn)段樹(shù) 然后有可加減性

呃 。。。 這么說(shuō)好像還是有點(diǎn)生澀

那么就拿poj2104來(lái)舉例子吧 慢慢講我覺(jué)得會(huì)很好的

題意就是給你一個(gè)100000長(zhǎng)度的數(shù)字 然后100000次詢(xún)問(wèn)［L，R］之間第k大的數(shù)字是多少

這個(gè)很容易看出來(lái) 暴力根本不可以 黑你分分鐘的事情啊 

我們?cè)趺崔k呢 想想線(xiàn)段樹(shù)能不能做 想來(lái)想去 一顆線(xiàn)段樹(shù)好像不能這么做 GG

那么我們做一個(gè)美好的假設(shè)：

我們建立100000棵美麗的線(xiàn)段樹(shù) 每一個(gè)線(xiàn)段樹(shù)的節(jié)點(diǎn) 表示這一個(gè)區(qū)間內(nèi)有多少個(gè)數(shù)字

第一棵線(xiàn)段樹(shù)保存著把第一個(gè)數(shù)字插入進(jìn)去之后 每個(gè)區(qū)間有多少個(gè)數(shù)字

第二棵線(xiàn)段樹(shù)保存著把第一個(gè) 第二個(gè)數(shù)字插入進(jìn)去之后 每個(gè)區(qū)間有多少個(gè)數(shù)字

。

。

。

。

第n棵線(xiàn)段樹(shù)保存著把第1，2，3。。。。n個(gè)數(shù)字插入進(jìn)去之后 每個(gè)區(qū)間有多少個(gè)數(shù)字

好了 我們已經(jīng)建立了這么多的線(xiàn)段樹(shù) 我們接下來(lái)該怎么辦呢？

對(duì) 就是查詢(xún) 

可是如何查詢(xún)呢？ 假設(shè)我們要查詢(xún)［l，r］內(nèi)的第k大

我們可以拿出第l－1 ，r 棵線(xiàn)段樹(shù)，然后兩者相減 我們想一下 這樣不就得到了相當(dāng)于插入了第l到r個(gè)點(diǎn)所建立的一棵線(xiàn)段樹(shù) 這棵線(xiàn)段樹(shù)每個(gè)節(jié)點(diǎn)保留的信息是：這個(gè)區(qū)間內(nèi)數(shù)字的個(gè)數(shù) 然后我們往下二分查找 就可以得到第k大了

現(xiàn)在的問(wèn)題時(shí) 這么龐大的空間開(kāi)銷(xiāo)我們耗費(fèi)不起 我們?cè)撊绾谓⑦@樣的線(xiàn)段樹(shù)呢？

答案就是 我們要盡量利用重復(fù)節(jié)點(diǎn) 

我們可以想一下 我們每次建立線(xiàn)段樹(shù) 相對(duì)于前一棵線(xiàn)段樹(shù) 我們只修改了它的一條路徑 最多只有l(wèi)ogn的變化 那么我們就存下這logn的變化 盡可能的利用重復(fù)節(jié)點(diǎn) 就可以達(dá)到重復(fù)使用的目的 有張圖你們自己體會(huì)一下 我也是盜圖 侵刪～

每次只修改一條路徑

這樣就能完成我們的主席樹(shù)了 

接下來(lái)是我自己寫(xiě)的該題代碼 

#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];//定義一個(gè)結(jié)構(gòu)體吧 要不心累 l 和 r 表示 左右兩個(gè)節(jié)點(diǎn)的序號(hào) 這個(gè)不是單純的單個(gè)線(xiàn)段樹(shù)了 這個(gè)還是有必要的 最好開(kāi)20-40倍int tree_cnt[maxn];//每個(gè)線(xiàn)段樹(shù)跟節(jié)點(diǎn)的坐標(biāo) 這個(gè)是搜索的起點(diǎn)啊int init[maxn];//int cop[maxn];int n,t_cnt=0,newn;//t_cnt是現(xiàn)在數(shù)組開(kāi)到多大了 然后建立下一個(gè)的時(shí)候注意++t_cnt;int getid(int x) {return (int)(lower_bound(init,init+newn,x)-init);}//數(shù)據(jù)太大 需要離散化int insert(int num,int becopyed,int l,int r)//記住返回自己的坐標(biāo){    ++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);}//一邊做減法 一邊查詢(xún)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;}