一：静态主席树
推荐的博客： http://www.cnblogs.com/zyf0163/p/4749042.html
静态的主席树和划分树类似，只不过是用的线段树存放。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N = 100000 + 5; int a[N], b[N], rt[N * 20], ls[N * 20], rs[N * 20], sum[N * 20]; //rt[i]表示处理完前i个数之后所形成的线段树 //sum[i]表示当前l-r范围内有几个点被更新了 //ls[i]表示编号为rt[i]这个点的左儿子为rt[ls[i]] //那么rt[r] - rt[l-1]即表示处理的[l, r]区间,对应点的sum相减 //到区间[l, r]的数要查询第k大便很容易了，设左节点中存的个数为cnt，当k<=cnt时，我们直接查询左儿子中第k小的数即可，如果k>cnt，我们只要去查右儿子中第k-cnt小的数即可 int n, k, tot, sz, ql, qr, x, q, T; void Build(int& o, int l, int r){ o = ++ tot; sum[o] = 0; if(l == r) return; int m = (l + r) >> 1; Build(ls[o], l, m); Build(rs[o], m + 1, r); } void update(int& o, int l, int r, int last, int p){ o = ++ tot; ls[o] = ls[last]; rs[o] = rs[last]; sum[o] = sum[last] + 1; if(l == r) return; int m = (l + r) >> 1; if(p <= m) update(ls[o], l, m, ls[last], p); else update(rs[o], m + 1, r, rs[last], p); } int query(int ss, int tt, int l, int r, int k){ if(l == r) return l; int m = (l + r) >> 1; int cnt = sum[ls[tt]] - sum[ls[ss]]; if(k <= cnt) return query(ls[ss], ls[tt], l, m, k); else return query(rs[ss], rs[tt], m + 1, r, k - cnt); } void work(){ scanf("%d%d%d", &ql, &qr, &x); int ans = query(rt[ql - 1], rt[qr], 1, sz, x); printf("%d ", b[ans]); } int main(){ scanf("%d", &T); while(T--){ scanf("%d%d", &n, &q); for(int i = 1; i <= n; i ++) scanf("%d", a + i), b[i] = a[i]; sort(b + 1, b + n + 1); sz = unique(b + 1, b + n + 1) - (b + 1); tot = 0; Build(rt[0],1, sz); //for(int i = 0; i <= 4 * n; i ++)printf("%d,rt = %d,ls = %d, rs = %d, sum = %d ", i, rt[i], ls[i], rs[i], sum[i]); for(int i = 1; i <= n; i ++)a[i] = lower_bound(b + 1, b + sz + 1, a[i]) - b; for(int i = 1; i <= n; i ++)update(rt[i], 1, sz, rt[i - 1], a[i]); //for(int i = 0; i <= 5 * n; i ++)printf("%d,rt = %d,ls = %d, rs = %d, sum = %d ", i, rt[i], ls[i], rs[i], sum[i]); while(q --)work(); } return 0; }
但静态主席树仍无法修改初始区间的信息。
二：动态主席树
使用了树状数组来存放前缀线段树，即树状数组中的每一个点都是线段树。但这棵线段树不再保存每个前缀的信息了，而是由树状数组的sum函数计算出这个前缀的信息，那么显而易见这棵线段树保存的是辅助数组S的值，即S=A[i-lowbit+1]+...+A[i],其中A[i]表示值为i的元素出现的次数。然后初始时建立一颗静态的主席树，树状数组只保存每次修改的信息。
表示不明白，大概能用。
#include<algorithm> #include<iostream> #include<string.h> #include<sstream> #include<stdio.h> #include<math.h> #include<vector> #include<string> #include<queue> #include<set> #include<map> using namespace std; const int INF=0x3f3f3f3f; const int maxn=60010; const int maxm=2500010; int ls[maxm],rs[maxm],c[maxm];//ls,rs左右儿子指针。c存值的个数 int arr[maxn],H[maxn],T[maxn];//arr存原序列.H存排序后值。T[i]第i棵线段树的根 int s[maxn],ua[maxn],ub[maxn],*use;//s为树状数组结点。当然也是线段树的根啦。 int n,m,tot; struct node { int l,r,k; } qs[10010];//由于要先hash。 void init()//hash初始化 { sort(H,H+m); m=unique(H,H+m)-H; } int Hash(int x)//查询x在排好序后的数组中出现的地址。 { return lower_bound(H,H+m,x)-H; } int build(int L,int R)//建空树 { int rt=tot++,mid; c[rt]=0; if(L!=R) { mid=(L+R)>>1; ls[rt]=build(L,mid); rs[rt]=build(mid+1,R); } return rt; } int Insert(int prt,int x,int val)//向空树中插入节点。val==-1时相当于删除点。 { //nrt为当前处于线段树的哪个点上。 int nrt=tot++,tp=nrt,l=0,r=m-1,mid; c[nrt]=c[prt]+val; while(l<r)//非递归插入。节省内存。 { mid=(l+r)>>1; if(x<=mid) { ls[nrt]=tot++,rs[nrt]=rs[prt];//共享结点 prt=ls[prt],nrt=ls[nrt]; r=mid; } else { ls[nrt]=ls[prt],rs[nrt]=tot++; prt=rs[prt],nrt=rs[nrt]; l=mid+1; } //cout<<nrt<<endl; c[nrt]=c[prt]+val; } return tp; } int lowbit(int x) { return x&(-x); } void update(int x,int p,int d)//树状数组更新,判断更新的是那几个线段树 { while(x<=n) { s[x]=Insert(s[x],p,d); x+=lowbit(x); } } int sum(int x) { int ret=0; while(x) { ret+=c[ls[use[x]]]; x-=lowbit(x); } return ret; } int qu(int L,int R,int k)//查询函数 { int lrt=T[L-1],rrt=T[R],l=0,r=m-1,mid,tp,i,sa,sb; for(i=L-1,use=ua;i;i-=lowbit(i)) use[i]=s[i]; sb=sum(L-1); for(i=R ,use=ub;i;i-=lowbit(i)) use[i]=s[i]; sa=sum(R); while(l<r) { mid=(l+r)>>1; tp=sa-sb+c[ls[rrt]]-c[ls[lrt]];//初始值加改变值 if(k<=tp) { r=mid; lrt=ls[lrt],rrt=ls[rrt]; for(i=L-1,use=ua;i;i-=lowbit(i)) use[i]=ls[use[i]];//计算对应子树改变 sb=sum(L-1); for(i=R ,use=ub;i;i-=lowbit(i)) use[i]=ls[use[i]]; sa=sum(R); } else { l=mid+1; k-=tp; lrt=rs[lrt],rrt=rs[rrt]; for(i=L-1,use=ua;i;i-=lowbit(i)) use[i]=rs[use[i]]; sb=sum(L-1); for(i=R ,use=ub;i;i-=lowbit(i)) use[i]=rs[use[i]]; sa=sum(R); } } return l; } int main() { int i,q,cas; char op[10]; scanf("%d",&cas); while(cas--) { scanf("%d%d",&n,&q); tot=m=0; for(i=1;i<=n;i++) scanf("%d",&arr[i]),H[m++]=arr[i]; for(i=0;i<q;i++) { scanf("%s",op); if(op[0]=='Q') scanf("%d%d%d",&qs[i].l,&qs[i].r,&qs[i].k); else { scanf("%d%d",&qs[i].l,&qs[i].r); qs[i].k=-INF,H[m++]=qs[i].r; } } init(); T[0]=build(0,m-1); for(i=1;i<=n;i++) T[i]=Insert(T[i-1],Hash(arr[i]),1); for(i=1;i<=n;i++) s[i]=T[0]; for(i=0;i<q;i++) { if(qs[i].k==-INF)//更改操作相当于先将原来的数删除后再插入新的。 { update(qs[i].l,Hash(arr[qs[i].l]),-1); update(qs[i].l,Hash(qs[i].r),1); arr[qs[i].l]=qs[i].r;//开始忘了改这里无限wa啊。。。 } else printf("%d ",H[qu(qs[i].l,qs[i].r,qs[i].k)]); } } return 0; }