主席树——多棵线段树的集合
主席樹：
（不要管名字）
我們有的時候，會遇到很多種情況，對于每一種情況，都需要通過線段樹的操作實現(xiàn)。
碰巧的是，相鄰兩種情況下的線段樹的差異不大。（總體的差異次數(shù)是O(N)級別的，均攤就是O(常數(shù))的了）
?
顯然的是，我們不能對于每種情況都建造一棵線段樹。n^n 空間直接MLE無疑。
救命稻草是：發(fā)現(xiàn)相鄰兩種情況下的線段樹的差異不大。
所以，我們是否可以讓不同的線段樹共用同一個節(jié)點(diǎn)呢？！？！？
這就是主席樹的本質(zhì)。也是精妙之處所在。
代碼實現(xiàn)不是很麻煩。
我一般用傳返回值形式，每次返回一個節(jié)點(diǎn)編號，便于設(shè)置兒子編號。比較方便。
注意的是，我們必須記錄lson，rson，不能采用x<<1,x<<1|1的形式。因為沒有這樣的規(guī)律可循。
你不知道子節(jié)點(diǎn)和自己有什么關(guān)系。（這是誰家的孩子？公家的）
?
?
經(jīng)典例題：
1.區(qū)間第k小（大）。
離散化必須的。
對于每一個區(qū)間節(jié)點(diǎn)開一個權(quán)值線段樹 。i的線段樹的節(jié)點(diǎn)l~r表示，在真正的區(qū)間1~i中，大小在l~r的數(shù)出現(xiàn)的次數(shù)。
記錄每個線段樹節(jié)點(diǎn)根的所在位置。
查詢的時候，l-1，r兩棵線段樹同時出發(fā)，區(qū)間[a,b]sum值做一個差，就是l~r這個區(qū)間內(nèi)，數(shù)值在[a,b]之間的數(shù)的個數(shù)。
對于區(qū)間第k小，選擇左兒子區(qū)間做差，u<k，就進(jìn)入右兒子，同時k-=u
否則進(jìn)入左兒子。
區(qū)間第k大正相反。
?
對于n棵主席樹，相鄰兩個主席樹i，i-1只在i的數(shù)值位置的值不一樣。
所以，相鄰的主席樹只會增加logn個節(jié)點(diǎn)。
總空間復(fù)雜度nlogn
代碼：
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int n,m; int a[N],num[N]; int cnt,rt[N]; int li(int x){return lower_bound(num+1,num+cnt+1,x)-num; } struct node{int sum,lson,rson; }t[N*18]; int tot; int add(int x,int l,int r,int c){tot++;int ret=tot;t[tot].sum=t[x].sum+1;if(l==r){return ret;}int mid=(l+r)>>1;if(c<=mid){t[tot].rson=t[x].rson;t[tot].lson=add(t[x].lson,l,mid,c);} else{t[tot].lson=t[x].lson;t[tot].rson=add(t[x].rson,mid+1,r,c);}return ret; } int query(int x,int y,int l,int r,int k){if(l==r){return l;}int mid=(l+r)>>1;int u=t[t[y].lson].sum-t[t[x].lson].sum;if(u>=k){return query(t[x].lson,t[y].lson,l,mid,k);}else{return query(t[x].rson,t[y].rson,mid+1,r,k-u);} } int main() {scanf("%d%d",&n,&m);int df;for(int i=1;i<=n;i++) scanf("%d",&a[i]),num[++cnt]=a[i];sort(num+1,num+cnt+1);cnt=unique(num+1,num+cnt+1)-num-1;rt[0]=++tot;for(int i=1;i<=n;i++) rt[i]=add(rt[i-1],1,cnt,li(a[i]));int op,l,r;while(m--){scanf("%d%d%d",&l,&r,&op);int ot=query(rt[l-1],rt[r],1,cnt,op);printf("%d\n",num[ot]);}ret?
2.spoj 10628 Count on a tree
給定一棵N個節(jié)點(diǎn)的樹，每個點(diǎn)有一個權(quán)值，對于M個詢問(u,v,k)，你需要回答u xor lastans和v這兩個節(jié)點(diǎn)間第K小的點(diǎn)權(quán)。其中l(wèi)astans是上一個詢問的答案，初始為0，即第一個詢問的u是明文。
?
樹上區(qū)間第k小，從根節(jié)點(diǎn)開始每個節(jié)點(diǎn)建主席樹，從父親版本跟新過來。
對于x的主席樹，[a,b]表示，從根到x的路徑上，點(diǎn)權(quán)值在[a,b]之間的點(diǎn)數(shù)。
兒子和父親的主席樹的差異，僅在x的點(diǎn)權(quán)數(shù)值的位置上。
類似樹上差分，
對于詢問的x，y，設(shè)它們的最近公共祖先是lca
四棵樹同時走，x，y路徑上的點(diǎn)權(quán)點(diǎn)數(shù)的信息，就是sum[x]+sum[y]-sum[lca]-sum[fa[lca]]（和點(diǎn)覆蓋的樹上差分類似）
剩下的同理了
代碼：
#include<bits/stdc++.h> using namespace std; const int N=100000+10; int n,m; int w[N]; int rt[N]; int num[N],mem; struct node{int nxt,to; }e[2*N]; int hd[N],cnt; int li(int x){return lower_bound(num+1,num+mem+1,x)-num; } void add(int x,int y){e[++cnt].nxt=hd[x];e[cnt].to=y;hd[x]=cnt; } int dep[N]; int fa[N][30];int lca(int x,int y){if(dep[x]<dep[y]) swap(x,y);for(int i=28;i>=0;i--){if(dep[fa[x][i]]>=dep[y])x=fa[x][i];}if(x==y) return x;for(int i=28;i>=0;i--){if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];}return fa[x][0]; } struct tr{int sum,lson,rson;#define ls(x) t[x].lson#define rs(x) t[x].rson#define s(x) t[x].sum }t[N*30]; int tot; int upda(int x,int l,int r,int c){int ret=++tot;t[ret].sum=t[x].sum+1;if(l==r) return ret;int mid=l+r>>1;if(c<=mid){rs(ret)=rs(x);ls(ret)=upda(ls(x),l,mid,c);}else{ls(ret)=ls(x);rs(ret)=upda(rs(x),mid+1,r,c);}return ret; } int query(int x,int y,int z,int p,int l,int r,int k){if(l==r) return l;int mid=l+r>>1;int u=s(ls(x))+s(ls(y))-s(ls(p))-s(ls(z));if(k<=u)return query(ls(x),ls(y),ls(z),ls(p),l,mid,k);else return query(rs(x),rs(y),rs(z),rs(p),mid+1,r,k-u); } void dfs(int x,int d){dep[x]=d;rt[x]=upda(rt[fa[x][0]],1,mem,li(w[x]));for(int i=hd[x];i;i=e[i].nxt){int y=e[i].to;if(y==fa[x][0]) continue;fa[y][0]=x;dfs(y,d+1); } } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&w[i]),num[++mem]=w[i];sort(num+1,num+mem+1);mem=unique(num+1,num+mem+1)-num-1;int x,y;for(int i=1;i<=n-1;i++){scanf("%d%d",&x,&y);add(x,y);add(y,x);}dfs(1,1);dep[0]=-1;for(int i=1;(1<<i)<=n;i++)for(int j=1;j<=n;j++){fa[j][i]=fa[fa[j][i-1]][i-1];}int op;int las=0;while(m--){scanf("%d%d%d",&x,&y,&op);x^=las;int anc=lca(x,y);//cout<<" anc "<<anc<<endl;int ot=query(rt[x],rt[y],rt[anc],rt[fa[anc][0]],1,mem,op);las=num[ot];printf("%d\n",num[ot]);}return 0; } Count on a tree?
?
3.[國家集訓(xùn)隊]middle
一個長度為n的序列a，設(shè)其排過序之后為b，其中位數(shù)定義為b[n/2]，其中a,b從0開始標(biāo)號,除法取下整。
給你一個長度為n的序列s。
回答Q個這樣的詢問：s的左端點(diǎn)在[a,b]之間,右端點(diǎn)在[c,d]之間的子序列中，最大的中位數(shù)。
其中a<b<c<d。
位置也從0開始標(biāo)號。
我會使用一些方式強(qiáng)制你在線。
?
這個題就比較的巧妙了。不像之前的套路性的第k問題。
這個是真真正正地用主席樹替代了線段樹。
?
首先，對于區(qū)間中位數(shù)一個比較套路的做法是：
二分一個答案mid，把所有>=mid的數(shù)值設(shè)成1，<mid的值設(shè)為-1
查詢區(qū)間內(nèi)的和是否>=0（這個題是>=0，題意中，偶數(shù)項的中位數(shù)是中間的那兩個靠后的那一個）
是，中位數(shù)應(yīng)該更大，
否則，中位數(shù)只能更小。
先不考慮復(fù)雜度。
給[a,d]區(qū)間的數(shù)賦值為1、-1
這個題，區(qū)間都不是固定的。
但是，[b+1,c-1]的值是必選的。計算一下這個區(qū)間的和。
對于[a,b],[c,d]
因為要讓中位數(shù)盡可能的大。
所以，爭取選擇盡可能多的1
找一個[a,b]的最大后綴，[c,d]的最大前綴。
這三個和就是對于mid的最大的和了，可以進(jìn)行判斷。
?
因為多組詢問，而數(shù)組不會改變，
而離散化之后，中位數(shù)的值在1~n之間。
所以，對于每一個二分的mid值，建一棵線段樹。
線段樹以區(qū)間下標(biāo)為下標(biāo)，記錄區(qū)間和，區(qū)間最大后綴，最大前綴。
就可以O(shè)(logn)判斷mid是否可以更優(yōu)了。
?
空間又炸了。所以主席樹閃亮登場！！！
發(fā)現(xiàn)，對于mid變成mid+1，只有值為mid的數(shù)的值會從+1變成-1.
主席樹在前者的基礎(chǔ)上暴力修改。
每一個數(shù)就會改一次，所以均攤logn空間。、
?
時間復(fù)雜度：nlogn^2
空間復(fù)雜度：nlogn
?
代碼：(vector 記錄數(shù)字出現(xiàn)的位置）
#include<bits/stdc++.h> using namespace std; const int N=20000+10; int n,m; int a[N],num[N],mem; int rt[N]; int x1,x2,x3,x4; int li(int x){return lower_bound(num+1,num+mem+1,x)-num; } struct node{int sum,lmx,rmx;int lson,rson;bool ncl,ncr;#define s(x) t[x].sum#define ls(x) t[x].lson#define rs(x) t[x].rson#define lm(x) t[x].lmx#define rm(x) t[x].rmx#define cl(x) t[x].ncl#define cr(x) t[x].ncr }t[N*40]; int tot; vector<int>pos[N]; void pushup(int x){s(x)=s(ls(x))+s(rs(x));lm(x)=max(lm(ls(x)),s(ls(x))+lm(rs(x)));rm(x)=max(rm(rs(x)),s(rs(x))+rm(ls(x))); } int build(int l,int r){int id=++tot;if(l==r){if(li(a[l])<=1) s(id)=lm(id)=rm(id)=-1;else s(id)=lm(id)=rm(id)=1;return id;}int mid=l+r>>1;cl(id)=1;cr(id)=1;ls(id)=build(l,mid);rs(id)=build(mid+1,r);pushup(id);return id; } int upda(int x,int y,int l,int r,int to,int c,bool nc){if(!nc) {x=++tot;}if(l==r){s(x)=lm(x)=rm(x)=c;return x;}int mid=(l+r)>>1;if(to<=mid){if(!cr(x)) rs(x)=rs(y);if(!cl(x)){cl(x)=1;ls(x)=upda(x,ls(y),l,mid,to,c,0);}else{ls(x)=upda(ls(x),ls(y),l,mid,to,c,1);}}else{if(!cl(x)) ls(x)=ls(y);if(!cr(x)){cr(x)=1;rs(x)=upda(x,rs(y),mid+1,r,to,c,0);}else{rs(x)=upda(rs(x),rs(y),mid+1,r,to,c,1);}}pushup(x);return x; } int qs(int x,int l,int r,int L,int R){if(L<=l&&r<=R){return s(x);}int mid=l+r>>1;int ret=0;if(L<=mid) ret+=qs(ls(x),l,mid,L,R);if(mid<R) ret+=qs(rs(x),mid+1,r,L,R);return ret; } node ql(int x,int l,int r,int L,int R){if(L<=l&&r<=R){return t[x];}int mid=l+r>>1;if(L<=mid&&mid<R){node ret;node le=ql(ls(x),l,mid,L,R);node ri=ql(rs(x),mid+1,r,L,R);ret.sum=le.sum+ri.sum;ret.lmx=max(le.lmx,le.sum+ri.lmx);return ret;}else if(L<=mid){return ql(ls(x),l,mid,L,R);}else {return ql(rs(x),mid+1,r,L,R);} } node qr(int x,int l,int r,int L,int R){if(L<=l&&r<=R){return t[x];}int mid=l+r>>1;if(L<=mid&&mid<R){node ret;node le=qr(ls(x),l,mid,L,R);node ri=qr(rs(x),mid+1,r,L,R);ret.sum=le.sum+ri.sum;ret.rmx=max(ri.rmx,ri.sum+le.rmx);return ret;}else if(L<=mid){return qr(ls(x),l,mid,L,R);}else {return qr(rs(x),mid+1,r,L,R);} } bool che(int val){int sz=0;if(x2+1<=x3-1) sz=qs(rt[val],1,n,x2+1,x3-1);int sr=ql(rt[val],1,n,x3,x4).lmx;int sl=qr(rt[val],1,n,x1,x2).rmx;return (sl+sz+sr)>=0; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]),num[++mem]=a[i];sort(num+1,num+mem+1);mem=unique(num+1,num+mem+1)-num-1;for(int i=1;i<=n;i++){pos[li(a[i])].push_back(i);}rt[1]=build(1,n);for(int i=2;i<=mem;i++){for(int j=0;j<pos[i-1].size();j++){int go=pos[i-1][j];rt[i]=upda(rt[i],rt[i-1],1,n,go,-1,rt[i]>0);}}scanf("%d",&m);int las=0;int ch[6];while(m--){scanf("%d%d%d%d",&x1,&x2,&x3,&x4);ch[1]=(x1+las)%n;ch[2]=(x2+las)%n;ch[3]=(x3+las)%n;ch[4]=(x4+las)%n;sort(ch+1,ch+4+1);x1=ch[1]+1,x2=ch[2]+1,x3=ch[3]+1,x4=ch[4]+1;int l=1,r=mem;int ans=0;while(l<=r){int mid=l+r>>1;if(che(mid)) ans=mid,l=mid+1;else r=mid-1;}las=num[ans];printf("%d\n",las);}return 0; }?
轉(zhuǎn)載于:https://www.cnblogs.com/Miracevin/p/9368361.html
總結(jié)
以上是生活随笔為你收集整理的主席树——多棵线段树的集合的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【线段树 集合hash】bzoj437
- 下一篇： 初识机器学习——吴恩达《Machine