傳送門

如標題，主席樹模板

稍微介紹一下主席樹..

主席樹是很多個線段樹的結(jié)合體

利用了單點修改不會更新太多節(jié)點的結(jié)論（反正這一題是這樣..），后一個線段樹借用前面線段樹的節(jié)點，而對于更新的節(jié)點才開一個新的節(jié)點存儲數(shù)據(jù)，大大的節(jié)省了時間和空間

（除第一顆樹外其他樹的構(gòu)建只要log(n)的時間和空間）

具體還是看代碼吧

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const int N=200010; int n,m,a[N],b[N],cnt; int rt[N<<5],L[N<<5],R[N<<5],sz[N<<5]; //rt為根節(jié)點編號 //L[i]為節(jié)點i的左子樹編號,R[i]是節(jié)點i的右子樹編號 //sz[i]是以節(jié)點i為根的子樹的大小 inline int build(int l,int r) //建立第一顆線段樹，不解釋 {int root=++cnt;if(l==r) return root;int mid=l+r>>1;L[root]=build(l,mid);R[root]=build(mid+1,r); } inline int add(int l,int r,int k,int pre)//添加新節(jié)點 {int root=++cnt; sz[root]=sz[pre]+1;//因為每次添加的線段樹都比前一個線段樹多一個節(jié)點//所以sz也要比上一個線段樹多1if(l==r) return root; //如果到邊界就返回int mid=l+r>>1;L[root]=L[pre]; R[root]=R[pre]; //借用前面線段樹的節(jié)點if(k<=mid) L[root]=add(l,mid,k,L[pre]);//如果更新的值的位置在左子樹就添加新節(jié)點到左邊,并覆蓋L[root]else R[root]=add(mid+1,r,k,R[pre]);//反之就添加新節(jié)點到右邊,同樣要覆蓋return root;//返回新節(jié)點的編號 } inline int query(int l,int r,int hea,int las,int k)//查詢區(qū)間第k名 {if(l==r) return l; //如果到邊界就返回節(jié)點編號//找排名的基本操作int mid=l+r>>1,x=sz[L[las]]-sz[L[hea]]; if(x>=k) return query(l,mid,L[hea],L[las],k);return query(mid+1,r,R[hea],R[las],k-x); } int main() {cin>>n>>m;for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];sort(b+1,b+n+1);//排序int len=unique(b+1,b+n+1)-b-1;//去重rt[0]=build(1,len);//建樹for(int i=1;i<=n;i++){int t=lower_bound(b+1,b+len+1,a[i])-b;//在b中找<=a[i]的最大位置rt[i]=add(1,len,t,rt[i-1]);//加點 }int x,y,z;while(m--){scanf("%d%d%d",&x,&y,&z);printf("%d\n",b[query(1,len,rt[x-1],rt[y],z)]);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/LLTYYC/p/9536454.html

總結(jié)

以上是生活随笔為你收集整理的P3834 【模板】可持久化线段树 1（主席树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。