讓我們來看一個(gè)經(jīng)典的問題吧：
給定一個(gè)[1,n]的區(qū)間，m次操作抬吟，操作種類如下：
1 L R：查詢[L,R]的區(qū)間和
2 L R X：將[L,R]的值加上X
這種經(jīng)典問題萨咕，想必大家學(xué)過線段樹后都可以輕松解決。然而如果再增加一種操作：
3 K：回退到第K次修改操作的結(jié)果
可見火本，如果題目要求回溯到歷史版本危队，那么普通的線段樹就不能解決了，因?yàn)樵诿看胃虏僮骱蟾婆希€段樹存儲(chǔ)的內(nèi)容就發(fā)生了改變茫陆，如果不進(jìn)行特殊記錄，那么這種改變將是永久的擎析。因此簿盅，對(duì)于這種類型的題目，我們可以用到今天要討論的數(shù)據(jù)結(jié)構(gòu)——主席樹來進(jìn)行解決揍魂。
主席樹桨醋，嚴(yán)格來講應(yīng)該叫：函數(shù)式線段樹，是基于線段樹的一種數(shù)據(jù)結(jié)構(gòu)愉烙，常用于處理一些在線問題讨盒，關(guān)于在線離線的概念參考上一篇文章：在線和離線算法。事實(shí)上步责，主席樹就是多個(gè)線段樹的集合體返顺。
主席樹的實(shí)質(zhì)，就是以最初的線段樹作為模板蔓肯，通過"結(jié)點(diǎn)復(fù)用“的方式遂鹊，實(shí)現(xiàn)存儲(chǔ)多個(gè)線段樹。
對(duì)于文章開始的問題蔗包，觀察后可以發(fā)現(xiàn)秉扑，在2操作進(jìn)行后，在上一次修改后的線段樹上调限，最多修改O(logn)個(gè)結(jié)點(diǎn)（最遠(yuǎn)是從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)）舟陆。如果每次單獨(dú)新建一個(gè)線段樹，則會(huì)造成重復(fù)存儲(chǔ)耻矮，如圖所示：
淺藍(lán)色的結(jié)點(diǎn)是當(dāng)前修改操作時(shí)訪問的結(jié)點(diǎn)秦躯，白色結(jié)點(diǎn)為上一棵線段樹的結(jié)點(diǎn)。
如果對(duì)每次修改操作無差別復(fù)制一棵線段樹裆装，那么用于存儲(chǔ)節(jié)點(diǎn)的開銷是巨大的踱承，因?yàn)閷?duì)于單次修改倡缠，大部分結(jié)點(diǎn)都不曾被訪問修改。
通過“結(jié)點(diǎn)復(fù)用”的方式茎活，我們可以將這多棵線段樹壓縮成如下形式：
因此第i個(gè)線段樹只要通過保留除修改路徑外的第i-1棵線段樹的結(jié)點(diǎn)昙沦，再新增加至多O(logn)個(gè)結(jié)點(diǎn)。
rt[i]保存第i次操作的線段樹的根節(jié)點(diǎn)载荔，這樣盾饮，回退到第k次操作等價(jià)于rt[i]=rt[k]，我們的問題就迎刃而解啦身辨。
那么丐谋，怎么來建立一棵主席樹呢？針對(duì)文章開始的題目煌珊，下面給出實(shí)現(xiàn)步驟：
1. 創(chuàng)建根節(jié)點(diǎn)、左右兒子結(jié)點(diǎn)數(shù)組
int tot=0,rt[maxn*20],lson[maxn*20],rson[maxn*20],v[maxn*20],lz[maxn*20],a[maxn];
tot是每次新建的結(jié)點(diǎn)編號(hào)泌豆。
rt[i]是第i棵線段樹的根節(jié)點(diǎn)的編號(hào)定庵。
lson[x]和rson[x]是結(jié)點(diǎn)x的左右兒子結(jié)點(diǎn)的編號(hào)。
v[x]是結(jié)點(diǎn)x代表的區(qū)間的和踪危。
lz[x]是結(jié)點(diǎn)x的懶惰（lazy）值蔬浙。
a[i]是初始的第i個(gè)位置的值。
因?yàn)榻Y(jié)點(diǎn)每次至多更新O(logn)個(gè)贞远，所以數(shù)組范圍應(yīng)該在原來的20-50倍左右畴博。
2.區(qū)間更新的pushup和pushdown
void push_up(int x){
v[x]=v[lson[x]]+v[rson[x]];
}
void push_down(int x,int len){
if(lz[x]){
v[lson[x]]+=(len>>1)*lz[x];
v[rson[x]]+=(len-(len>>1))*lz[x];
lz[lson[x]]+=(len>>1)*lz[x];
lz[rson[x]]+=(len-(len>>1))*lz[x];
lz[x]=0;
}
}
區(qū)間更新基礎(chǔ)，不會(huì)的可以先了解線段樹的區(qū)間更新寫法蓝仲。
3. 建樹
void build(int &x,int l,int r){
x=++tot;
lz[x]=0;
if(l==r){
v[x]=a[l];
return;
}
int mid=l+r>>1;
build(lson[x],l,mid);
build(rson[x],mid+1,r);
push_up(x);
}
和線段樹的思想是一樣的俱病，只是在調(diào)用過程中，我們以引用的形式袱结，實(shí)現(xiàn)對(duì)rt,lson,rson的更新亮隙。
建樹的調(diào)用如下：
build(rt[0],1,n);
3. 更新
void update(int L,int R,int l,int r,int &x,int last,int val){
x=++tot;
lson[x]=lson[last];rson[x]=rson[last];lz[x]=lz[last];v[x]=v[last];
if(L<=l&&R>=r){
v[x]+=(r-l+1)*val;lz[x]+=val;
return;
}
push_down(x,r-l+1);
int mid=l+r>>1;
if(L<=mid) update(L,R,l,mid,lson[x],lson[last],val);
if(R>mid) update(L,R,mid+1,r,rson[x],rson[last],val);
push_up(x);
}
第1行開辟了新的結(jié)點(diǎn)，第2行進(jìn)行了結(jié)點(diǎn)復(fù)用垢夹，last就是上一棵線段樹的結(jié)點(diǎn)溢吻，從根節(jié)點(diǎn)向下更新。
更新的調(diào)用如下：
update(x,y,1,n,rt[i],rt[i-1],w);
4. 查詢
int query(int L,int R,int l,int r,int x){
if(L<=l&&R>=r){
return v[x];
}
push_down(x,r-l+1);
int mid=l+r>>1,sum=0;
if(L<=mid) sum+=query(L,R,l,mid,lson[x]);
if(R>mid) sum+=query(L,R,mid+1,r,rson[x]);
push_up(x);
return sum;
}
查詢就是簡單的區(qū)間查詢果元。
查詢的調(diào)用如下：
query(x,y,1,n,rt[i]);
5. 實(shí)現(xiàn)
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <functional>
#include <map>
#include <stack>
#include <ctime>
#include <sstream>
#include <bitset>
//#include<ext/pb_ds/assoc_container.hpp>
//#include <bits/stdc++.h>
#define REP(i,j,k) for(int (i)=(j);(i)<=(k);(i)++)
#define ERP(i,j,k) for(int (i)=(j);(i)>=(k);(i)--)
#define MEM(a,b) memset(a,b,sizeof(a))
#define NE putchar('\n')
#define SP putchar(' ')
#define fi first
#define sc second
#define mkp make_pair
#define pb push_back
#define all(a) a.begin(),a.end()
//#define lson l,mid,x<<1
//#define rson mid+1,r,x<<1|1
#define lowbit(x) ((x)&(-(x)))
#define lc(a) ch[(a)][0]
#define mod_add(a,b,m) (a+b>m?a+b-m:a+b)
#define mod_sub(a,b,m) (a-b<0?a-b+m:a-b)
using namespace std;
//using namespace __gnu_pbds;
typedef double DB;
typedef long double LDB;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL;
const DB eps=1e-6;
const DB Pi=acos(-1.0);
const ll mod=1e9+7;
const ull ha1=1e9+7;
const ull ha2=1e9+9;
const int maxn=1e5+10;
const int maxm=1e6+10;
const int inf=1e9+10;
//IO掛
template<typename Type>inline void read(Type&in){
in=0;Type f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){in=in*10+ch-'0';ch=getchar();}
in*=f;
}
template<typename Type>inline void out(Type o){
if(o<0){putchar('-');o=-o;}
if(o>=10) out(o/10);
putchar(o%10+'0');
}
/*Header*/
//printf("%d%c",a[i]," \n"[i==n]);
int tot=0,rt[maxn*20],lson[maxn*20],rson[maxn*20],v[maxn*20],lz[maxn*20],a[maxn];
void push_up(int x){
v[x]=v[lson[x]]+v[rson[x]];
}
void push_down(int x,int len){
if(lz[x]){
v[lson[x]]+=(len>>1)*lz[x];
v[rson[x]]+=(len-(len>>1))*lz[x];
lz[lson[x]]+=(len>>1)*lz[x];
lz[rson[x]]+=(len-(len>>1))*lz[x];
lz[x]=0;
}
}
void build(int &x,int l,int r){
x=++tot;
lz[x]=0;
if(l==r){
v[x]=a[l];
return;
}
int mid=l+r>>1;
build(lson[x],l,mid);
build(rson[x],mid+1,r);
push_up(x);
}
void update(int L,int R,int l,int r,int &x,int last,int val){
x=++tot;
lson[x]=lson[last];rson[x]=rson[last];lz[x]=lz[last];v[x]=v[last];
if(L<=l&&R>=r){
v[x]+=(r-l+1)*val;lz[x]+=val;
return;
}
push_down(x,r-l+1);
int mid=l+r>>1;
if(L<=mid) update(L,R,l,mid,lson[x],lson[last],val);
if(R>mid) update(L,R,mid+1,r,rson[x],rson[last],val);
push_up(x);
}
int query(int L,int R,int l,int r,int x){
if(L<=l&&R>=r){
return v[x];
}
push_down(x,r-l+1);
int mid=l+r>>1,sum=0;
if(L<=mid) sum+=query(L,R,l,mid,lson[x]);
if(R>mid) sum+=query(L,R,mid+1,r,rson[x]);
push_up(x);
return sum;
}
int x,y,w;
int main(){
int n,k,opt;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(rt[0],1,n);
for(int i=1;i<=k;i++){
cin>>opt;
if(opt==1){
rt[i]=rt[i-1];
cin>>x>>y;
cout<<query(x,y,1,n,rt[i])<<endl;
}
else if(opt==2){
cin>>x>>y>>w;
update(x,y,1,n,rt[i],rt[i-1],w);
}
else{
cin>>x;
rt[i]=rt[x];
}
}
return 0;
}
對(duì)于第i個(gè)操作促王，方式1通過rt[i-1]更新rt[i]，方式2通過引用更新rt[i]而晒，方式3通過rt[x]更新rt[i]渊季。
6. 測試一下～
input.txt
10 8
1 2 3 4 5 6 7 8 9 10
2 6 7 2
1 6 7
2 3 5 4
1 3 5
2 1 9 5
1 1 9
3 3
1 1 10
output.txt
17
24
106
71
正確無誤～(blink)
那么，主席樹的入門就到這里了磅废，下面給出poj 2104（靜態(tài)區(qū)間求第K大）的主席樹代碼映穗，作為參考啦～
#include <bits/stdc++.h>
#include <cstdio>
#define fi first
#define sc second
#define mkp make_pair
#define pb push_back
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL;
const double eps=1e-8;
const double pi=acos(-1);
const int mod=1e9+7;
/*Header*/
const int maxn=1e5+10;
int rt[maxn*20],lson[maxn*20],rson[maxn*20],sum[maxn*20];
int a[maxn],b[maxn];
int tot;
int n,q;
void build(int &x,int l,int r){
x=++tot;
sum[x]=0;
if(l==r) return;
int mid=(l+r)>>1;
build(lson[x],l,mid);
build(rson[x],mid+1,r);
}
void update(int &x,int last,int l,int r,int pos){
x=++tot;
lson[x]=lson[last];
rson[x]=rson[last];
sum[x]=sum[last]+1;
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) update(lson[x],lson[last],l,mid,pos);
else update(rson[x],rson[last],mid+1,r,pos);
}
int query(int L,int R,int l,int r,int k){
if(l==r) return l;
int mid=(l+r)>>1;
int cnt=sum[lson[R]]-sum[lson[L]];
if(k<=cnt) return query(lson[L],lson[R],l,mid,k);
else return query(rson[L],rson[R],mid+1,r,k-cnt);
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+1+n);
int m=unique(b+1,b+1+n)-(b+1);
tot=0;
build(rt[0],1,m);
for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+m,a[i])-b;
for(int i=1;i<=n;i++) update(rt[i],rt[i-1],1,m,a[i]);
int x,y,k,ans;
while(q--){
scanf("%d %d %d",&x,&y,&k);
ans=query(rt[x-1],rt[y],1,m,k);
printf("%d\n",b[ans]);
}
}
return 0;
}
