在学习主席树之前
你必须学习：- 线段树。
- 前缀和。
- sort函数、unique函数以及lower_bound函数的使用方法。
什么是主席树
主席树又叫函数式线段树，又名可持久化线段树。所以主席树的名称与他的功能一点关系都没有。 主席树的时空复杂度为$O(n logn)$。主席树的模板
由于主席树比较难理解，所以结合代码理解一下：|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
struct node{ int l,r,sum,cnt;//分别表示左儿子、右儿子、和、子节点中叶子节点个数 }tree[MAXN*20];//主席树与线段树不同，因为主席树中包含着许多线段树，所以内存调大 void insert(int &x,int y,int l,int r,int p){ x=++ntt;//编号 tree[x]=tree[y];//先复制上一个节点 if(l==r){//叶子节点 tree[x].sum+=p;//和增加 tree[x].cnt++;//个数增加 return ; } int mid=(l+r)>>1;//与线段树差不多 if(p<=mid) insert(tree[x].l,tree[y].l,l,mid,p); else insert(tree[x].r,tree[y].r,mid+1,r,p); tree[x].sum=tree[tree[x].l].sum+tree[tree[x].r].sum;//pushup tree[x].cnt=tree[tree[x].l].cnt+tree[tree[x].r].cnt; } int Sum(int x,int y,int l,int r,int L,int R){//求[l,r]区间中满足值在[L,R]区间的和 if(L>R) return 0;//没有该区间 if(L<=l&&r<=R){//符合条件 return tree[x].sum-tree[y].sum; } int mid=(l+r)>>1,res=0;//和线段树差不多 if(L<=mid) res+=Sum(tree[x].l,tree[y].l,l,mid,L,R); if(R>mid) res+=Sum(tree[x].r,tree[y].r,mid+1,r,L,R); return res; } int Cnt(int x,int y,int l,int r,int L,int R){//求[l,r]区间中满足值在[L,R]区间的叶子节点个数 if(L>R) return 0;//没有该区间 if(l>r) return 0;//没有该区间 if(L<=l&&r<=R){//符合条件 return tree[x].cnt-tree[y].cnt; } int mid=(l+r)>>1,res=0;//与线段树差不多 if(L<=mid) res+=Cnt(tree[x].l,tree[y].l,l,mid,L,R); if(R>mid) res+=Cnt(tree[x].r,tree[y].r,mid+1,r,L,R); return res; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include<bits/stdc++.h> #define int long long #define MAXN 200010 using namespace std; int n,m,q,t=0; int a[MAXN],b[MAXN],rt[MAXN]; struct node{ int l,r,sum; }tree[MAXN*20]; void lsh(){ sort(b+1,b+n+1); m=unique(b+1,b+n+1)-(b+1); for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+m+1,a[i])-b; } void insert(int y,int &x,int l,int r,int p){ x=++t; tree[x]=tree[y]; tree[x].sum++; if(l==r) return; int mid=(l+r)>>1; if(p<=mid) insert(tree[y].l,tree[x].l,l,mid,p); else insert(tree[y].r,tree[x].r,mid+1,r,p); } int query(int x,int y,int l,int r,int k){ if(l==r) return l; int tmp=tree[tree[y].l].sum-tree[tree[x].l].sum; int mid=(l+r)>>1; if(k<=tmp) return query(tree[x].l,tree[y].l,l,mid,k); else return query(tree[x].r,tree[y].r,mid+1,r,k-tmp); } signed main(){ cin>>n>>q; for(int i=1;i<=n;i++){ cin>>a[i]; b[i]=a[i]; } lsh(); for(int i=1;i<=n;i++) insert(rt[i-1],rt[i],1,m,a[i]); for(int l,r,k,i=1;i<=q;i++){ cin>>l>>r>>k; cout<<b[query(rt[l-1],rt[r],1,m,k)]<<endl; } return 0; } |
所以说您还没有理解主席树，只会板子对吗