?何為主席樹

?　　　　　　　　　　^_圖1?

主席樹的構造如圖，以前序遍歷的方式編號，葉子表示1到n

因為葉子是1到n，就有了左子樹總是小于右子樹的性質

除葉子外的節點記錄的是區間sum代表這個節點的葉子有多少個數

如圖 區間[2,2]有1個數，區間[3,3]有1個數

所以區間[1,2]有1個數，區間[3,4]有2個數，區間[1,4]有3個數

?性質

• 左子樹總是小于右子樹

因為從左到右葉子是1到n

　　? ?設樹的sum=x+y，左子樹sum=x，右子樹sum=y

所以在找第k小的時候,由于左子樹小于右子樹，所以前x小肯定在左子樹上，第x+1到第x+y小在右子樹上

　　? ?當k<=x時，就在左子樹上找，當k>x時在右子樹上找，

　　? ?在右子樹上找時，由于右子樹第一個是第x+1小，所以找第k小也就是找右子樹的第k-x小

• 區間可減性

　由于sum記錄的是個數，假設現在是第L棵樹，經過n次操作變成第R棵樹

　由于每次操作都是修改一次，所以R的左子樹sum-L的左子樹sum=從L到R的左子樹的操作數

　所以求[L,R]區間的第k小，可以利用R的左子樹sum-L的左子樹sum即為[L,R]內左子樹上的數的個數

^{?　　　　　　　　　　　　　　　　　　　　圖2}

?

如圖 經過(L,R]區間的增加的左子樹的個數為2，也就是R的左子樹sum-L的左子樹的sum

?

?例題

洛谷3919

這個題是可持久化的題，并非完全的主席樹

這個題的葉子的值不是1到n，而是根據輸入而定

也沒有用到上述的性質

利用這個題來學習可持久化，為主席樹做鋪墊

1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e6+5; 4 struct Node 5 { 6 int l,r; 7 int num;///num為值，這里與主席樹不同 8 Node(){num=0;} 9 }seg[maxn*20]; 10 int root[maxn],a[maxn]; 11 int cnt=0; 12 void build(int l,int r,int &rt)///以前序遍歷的方式建樹 13 { 14 rt=++cnt;///rt為編號 15 if(l==r) 16 { 17 seg[rt].num=a[l]; 18 return ; 19 } 20 int mid=(r+l)>>1; 21 build(l,mid,seg[rt].l); 22 build(mid+1,r,seg[rt].r); 23 } 24 25 void update(int l,int r,int &rt,int pos,int y) 26 { 27 seg[++cnt]=seg[rt];///復制前一棵樹 28 rt=cnt;///處理所新建的這棵樹 29 if(l==r) 30 { 31 seg[rt].num=y; 32 return ; 33 } 34 int mid=(r+l)>>1; 35 if(pos<=mid) update(l,mid,seg[rt].l,pos,y); 36 else update(mid+1,r,seg[rt].r,pos,y); 37 } 38 39 int query(int l,int r,int rt,int pos) 40 { 41 if(l==r) return seg[rt].num; 42 int mid=(r+l)>>1; 43 if(pos<=mid) return query(l,mid,seg[rt].l,pos); 44 else return query(mid+1,r,seg[rt].r,pos); 45 } 46 47 int main() 48 { 49 ios::sync_with_stdio(0); 50 int n,m; 51 cin>>n>>m; 52 for(int i=1;i<=n;i++) 53 cin>>a[i]; 54 build(1,n,root[0]); 55 int pre,op,x,y; 56 for(int i=1;i<=m;i++) 57 { 58 cin>>pre>>op>>x; 59 if(op==1) 60 { 61 cin>>y; 62 root[i]=root[pre]; 63 update(1,n,root[i],x,y); 64 } 65 else 66 { 67 cout<<query(1,n,root[pre],x)<<endl; 68 root[i]=root[pre]; 69 } 70 } 71 } View Code

poj2104

主席樹的模板題，用到了上述的性質

由于剛開始沒有值，我就沒有建樹

其實做模板的話可以建一個空樹

由于葉子是從1到n的，所以對于給出的數一般要離散化一下，使得對應1到n

1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 #define ll long long 5 const int maxn=1e5+5; 6 int cnt,root[maxn];///每棵樹的根 7 int index[maxn];///按值大小排序后的序號 8 struct node 9 { 10 int l,r; 11 int sum; 12 node(){sum=0;} 13 }seg[maxn*40]; 14 struct value 15 { 16 int v; 17 int id; 18 }V[maxn]; 19 bool cmp(value a,value b) 20 { 21 return a.v<b.v; 22 } 23 24 void init() 25 { 26 cnt=0; 27 seg[0].l=0,seg[0].r=0; 28 root[0]=0; 29 } 30 31 void build(int l,int r,int &rt)///以前序遍歷的方式建樹 32 { 33 rt=++cnt;///rt為編號 34 if(l==r) 35 return ; 36 int mid=(r+l)>>1; 37 build(l,mid,seg[rt].l); 38 build(mid+1,r,seg[rt].r); 39 } 40 41 void update(int l,int r,int &rt,int pos) 42 { 43 seg[++cnt]=seg[rt];///復制前一棵樹 44 rt=cnt;///因為對新樹進行操作，是rt為新樹 45 seg[rt].sum++;///進行操作了，個數+1 46 47 if(l==r) return ; 48 int mid=(l+r)>>1; 49 if(mid>=pos) 50 update(l,mid,seg[rt].l,pos); 51 else 52 update(mid+1,r,seg[rt].r,pos); 53 } 54 55 int query(int L,int R,int l,int r,int k) 56 { 57 int d=seg[seg[R].l].sum-seg[seg[L].l].sum;///利用區間可減性，左子樹上一共有d個數 58 if(l==r) return l; 59 int mid=(l+r)>>1; 60 if(d>=k)///利用 左子樹<右子樹 前d個在左子樹上，其他的在右子樹上 61 return query(seg[L].l,seg[R].l,l,mid,k); 62 else///右子樹第一個是第d+1個 找第k個也就是找右子樹的第k-d個 63 return query(seg[L].r,seg[R].r,mid+1,r,k-d); 64 65 } 66 67 int main() 68 { 69 int n,m; 70 cin>>n>>m; 71 for(int i=1;i<=n;i++) 72 { 73 cin>>V[i].v; 74 V[i].id=i; 75 } 76 ///離散化 77 sort(V+1,V+1+n,cmp); 78 for(int i=1;i<=n;i++) 79 index[V[i].id]=i; 80 init(); 81 // build(1,n,root[0]); 82 for(int i=1;i<=n;i++) 83 { 84 root[i]=root[i-1];///復制前一個樹 85 update(1,n,root[i],index[i]); 86 } 87 int L,R,k; 88 for(int i=1;i<=m;i++) 89 { 90 cin>>L>>R>>k; 91 cout<<V[query(root[L-1],root[R],1,n,k)].v<<endl; 92 } 93 } View Code

?hdu4417

查詢$[L,R]$區間里有多少個數不大于k

只需要修改一下query函數

把k也離散化一下，利用k是第x小，答案就是

第R棵樹的[0,k]數量-第(L-1)棵樹的[0,k]數量

因為這個題是從$L,R\epsilon[0,n-1]$而不是從$1$開始，需要注意坑點

因為是從$1$到$n$的樹，需要記得$L++,R++$

因為離散化后會從$k\epsilon[0,n]$,所有需要從0開始建樹更新查詢，防止從$1$開始找不到$0$位置

1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e5+5; 4 struct node 5 { 6 int l,r; 7 int sum; 8 node(){sum=0;} 9 }seg[maxn*20]; 10 int root[maxn]; 11 int cnt=0; 12 int a[maxn],b[maxn]; 13 14 void Init() 15 { 16 cnt=0; 17 root[0]=0; 18 seg[0].l=0,seg[0].r=0; 19 } 20 21 void build(int l,int r,int &rt) 22 { 23 rt=++cnt; 24 if(l==r) return ; 25 int mid=(l+r)>>1; 26 build(l,mid,seg[rt].l); 27 build(mid+1,r,seg[rt].r); 28 } 29 30 void update(int l,int r,int &rt,int pos) 31 { 32 seg[++cnt]=seg[rt]; 33 rt=cnt; 34 seg[rt].sum++; 35 if(l==r) 36 return ; 37 int mid=(r+l)>>1; 38 if(pos<=mid) return update(l,mid,seg[rt].l,pos); 39 else return update(mid+1,r,seg[rt].r,pos); 40 } 41 42 43 ///query第R棵樹的[0,k]數量-第(L-1)棵樹的[0,k]數量 44 ///詢問方法1 45 int query1(int L,int R,int l,int r,int k) 46 { 47 if(l==r)///[0,k]中某個位置的增量 48 return seg[R].sum-seg[L].sum; 49 int mid=(l+r)>>1; 50 if(mid>=k) 51 return query(seg[L].l,seg[R].l,l,mid,k); 52 else///遞歸右子樹，需要加上左子樹的增量 53 { 54 int d=seg[seg[R].l].sum-seg[seg[L].l].sum; 55 return d+query(seg[L].r,seg[R].r,mid+1,r,k); 56 } 57 } 58 ///詢問方法2 59 int query2(int rt,int l,int r,int k) 60 { 61 if(l==r) 62 return seg[rt].sum; 63 int mid=(r+l)>>1; 64 if(mid>=k) 65 return query(seg[rt].l,l,mid,k); 66 else 67 return seg[seg[rt].l].sum+query(seg[rt].r,mid+1,r,k); 68 } 69 70 71 int main() 72 { 73 // freopen("C:\\Users\\14685\\Desktop\\C++workspace\\in&out\\contest","r",stdin); 74 int t; 75 cin>>t; 76 for(int T=1;T<=t;T++) 77 { 78 int n,m; 79 cin>>n>>m; 80 for(int i=1;i<=n;i++) 81 cin>>a[i],b[i]=a[i]; 82 83 sort(b+1,b+1+n); 84 int len=unique(b+1,b+n+1)-(b+1); 85 Init(); 86 build(0,len,root[0]); 87 for(int i=1;i<=n;i++) 88 { 89 root[i]=root[i-1]; 90 update(0,len,root[i],upper_bound(b+1,b+1+len,a[i])-b-1); 91 } 92 93 printf("Case %d:\n",T); 94 95 while(m--) 96 { 97 int L,R,k; 98 cin>>L>>R>>k; 99 L++,R++; 100 k=upper_bound(b+1,b+1+len,k)-b-1; 101 // cout<<query1(root[L-1],root[R],1,len,k)<<endl; 102 cout<<query2(root[R],0,len,k)-query2(root[L-1],0,len,k)<<endl; 103 } 104 } 105 } View Code

?

?

轉載于:https://www.cnblogs.com/MMMinoz/p/11440109.html

總結

以上是生活随笔為你收集整理的主席树之初见的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。