首页 > 代码库 > 主席树
主席树
POJ 2104 这题说的是给了一个区间求区间的第K大的数， 这点利用 函数式线段树的前缀式线段是的 长处 解决， 我们将 每个数字离散一下， 然后线段树存的是他的孩子个数，然后利用函数式线段树的前缀思想 两个前缀相减便得到了我们想要的 区间中的点的个数
#include <iostream>#include <string.h>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;const int maxn=7000005;const int MA = 100005;int Ls[maxn],Rs[maxn],num[maxn],T[MA],len;int dd[MA],vv[MA];void insert(int L, int R, int k, int pre, int &x){ x = ++len; Ls[x]=Ls[pre]; Rs[x]=Rs[pre]; num[x]=num[pre]+1; if(L==R) return ; int mid=(L+R)>>1; if(k<=mid) insert(L,mid,k,Ls[pre],Ls[x]); else insert(mid+1,R,k,Rs[pre],Rs[x]);}int query(int L, int R,int K, int pre,int cur){ if(L==R) return L; int mid = (L+R)>>1; if(num[ Ls[cur] ]-num[ Ls[pre] ]>=K) return query(L,mid,K,Ls[pre],Ls[cur]); else return query( mid+1, R, K - (num[Ls[cur]]-num[Ls[pre]]),Rs[pre],Rs[cur]);}int main(){ int n,m; while(scanf("%d%d",&n,&m)==2){ for(int i =0; i< n; ++i){ scanf("%d",&dd[i]); vv[i]=dd[i]; } sort(vv,vv+n); int vk= unique(vv,vv+n)-vv; T[0]=Ls[0]=Rs[0]=num[0]=len=0; for(int i =0; i<n;i++){ int loc = lower_bound(vv,vv+vk,dd[i])-vv+1; insert(1,vk,loc,T[i],T[i+1]); } while(m--){ int L,R,K; scanf("%d%d%d",&L,&R,&K); int ans=query(1,vk,K,T[L-1],T[R]); printf("%d\n",vv[ans-1]); } } return 0;}
zoj 2112 主席树+树状数组 这题说的是给了一个数组 然后 有两种操作第一种操作 是查询 【L，R】 中的第K 大的数 ， 第二种操作是 将x位置的值改为k， 这样同样利用 主席树前缀线段树的想法做好后，我们 用一个树状数组对它进行更改， 我们知道 在树状数组的 中 每个点就是一课树 然 后 通 过 不 断 地 去 更 改 这 树状数组的的 lowbit的树 结果求得了这个区间的 值
计算式 sum(R)-sum(L)+num(ls[rr])-num[rx[ll]]; 判断是进入左子树还是右子树
#include <iostream>#include <cstdio>#include <string.h>#include <cmath>#include <algorithm>using namespace std;const int maxn = 1009000 ;const int MM = 60005;struct Que{ int kind,L,R,K;}Q[10005];int dd[50005],vv[MM],T[50005],Ls[maxn],Rs[maxn],num[maxn],len,S[50005],use[50005];int n,m,vk;void insert(int L, int R, int loc, int v, int pre, int &x ){ x=++len; Ls[x] = Ls[ pre ]; Rs[x] = Rs[ pre ]; num[x] = num[ pre ] + v ; if( L == R )return; int mid = ( L + R ) >> 1; if( loc <= mid ) insert( L, mid, loc, v, Ls[pre], Ls[x] ); else insert( mid+1, R, loc, v, Rs[pre], Rs[x] );}int lowbit( int x ){ return x&(-x);}int sum(int x){ int ans=0; while(x>0){ ans += num[ Ls[ use[ x ] ] ]; x -= lowbit(x); } return ans;}void modie( int x, int loc, int v ){ while(x<=n){ insert( 0, vk-1, loc, v, S[x], S[x] ); x+=lowbit(x); }}int query(int L, int R, int left , int right, int K ,int LL, int RR){ if(L==R) return L; int mid =(L+R)>>1; int nm = sum(right) - sum(left) + num[ Ls[RR] ] - num[ Ls[LL] ]; if(nm>=K){ for(int i = left; i ; i -=lowbit(i)) use[i]=Ls[use[i]]; for(int i = right; i ; i -= lowbit(i) ) use[i]=Ls[use[i]]; return query( L, mid, left, right, K, Ls[LL] ,Ls[RR] ); }else{ for( int i = left ; i ; i -= lowbit(i) ) use[i]=Rs[ use[i] ]; for(int i= right ; i ; i-=lowbit(i) ) use[i]=Rs[ use[i] ]; return query(mid+1,R,left, right, K-nm, Rs[LL] ,Rs[RR] ); }}int main(){ int c; scanf("%d",&c); while(c--){ scanf("%d%d",&n,&m); vk=0; memset(S,0,sizeof(S)); for(int i=1; i<=n; ++i){ scanf("%d",&dd[i]); vv[vk++]=dd[i]; } char op[10]; for(int i =0; i < m; ++i){ scanf("%s",op); if(op[0]==‘Q‘){ Q[i].kind=0; scanf("%d%d%d",&Q[i].L,&Q[i].R,&Q[i].K); }else{ Q[i].kind=1; scanf("%d%d",&Q[i].L,&Q[i].R); vv[vk++] = Q[i].R; } } sort(vv,vv+vk); vk=unique(vv,vv+vk)-vv; T[0]=Rs[0]=Ls[0]=num[0]=len=0; for(int i=1; i<=n; i++) { int loc = lower_bound(vv,vv+vk,dd[i])-vv; insert(0,vk-1,loc,1,T[i-1],T[i]); } for( int i = 0; i < m; ++ i ) { if(Q[i].kind==0){ int LL=Q[i].L-1; int RR=Q[i].R; int K =Q[i].K; for(int i=LL ; i; i-=lowbit(i)) use[i]=S[i]; for(int i=RR ; i ; i-=lowbit(i) ) use[i]=S[i]; int ans = query(0, vk-1, LL, RR, K, T[LL], T[RR]); printf("%d\n",vv[ans]); }else{ int loc = lower_bound( vv , vv + vk , dd[Q[i].L] ) - vv ; modie( Q[i].L, loc , -1 ); loc = lower_bound( vv , vv+vk , Q[i].R ) - vv ; modie( Q[i].L, loc , 1 ); dd[Q[i].L] = Q[i].R; } } } return 0;}
的
主席树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。