前几天新打了一把主席树，感觉萌萌哒。个人感觉主席树像是线段树的增强版。先上一道主席树的模板题：对一个序列a，多次求区间[l,r]第K大是多少，要求解决每次询问的时间复杂度为O(log n)，n为元素个数。直观的想法就是从左到右扫，类似计数排序一样每遇到一个数x就在上一棵线段树的基础上对相应位置+1（权值线段树）。应为建n棵线段树时空消耗大，所以打个离散化+主席树就可以了。貌似并不是太高大上的算法。
主席树本身是静态的，不能支持对建好的线段树的修改操作（神犇请自动屏蔽）。那么如果想要每次对原序列进行单元素修改后再查询（区间修改的话orz~~），怎么做呢？没错就是树状数组套主席树，修改O(log^2n)，查询O(log^2n)。原来单靠一个主席树查询O(logn)，修改O(n^2)……可以说是对修改和查询的时间复杂度的平衡吧(然而我还不会如何建树状数组上的主席树，自己写的程序消耗内存n^2直接挂了，哪位神犇传授一下)。
下面直接上主席树代码，写了个struct，也不知道最近为什么喜欢打封装。
主席树：
1 struct PD_tree 2 { 3 private: 4 5 struct point 6 { 7 long s,e,sum;//sum is to record the number's num in [s,e] 8 point* lson,*rson; 9 }**root; 10 long leng,turn; 11 12 void mdy(point* now,long s,long e,long sum)//mordify one's point 13 { 14 now->s=s,now->e=e,now->sum=sum; 15 } 16 17 void work(long s,long e,point* &now)//be started with 18 { 19 long mid; 20 now=new point; 21 mdy(now,s,e,0); 22 if (s==e){ 23 now->lson=now->rson=NULL; 24 return; 25 } 26 mid=(s+e)/2; 27 work(s,mid,now->lson); 28 work(mid+1,e,now->rson); 29 } 30 31 void update(long pla,point* form,point* &now) 32 { 33 long s,e,mid; 34 s=form->s,e=form->e; 35 now=new point; 36 mdy(now,s,e,form->sum+1); 37 if (s==e)now->lson=now->rson=NULL; 38 else { 39 mid=(s+e)/2; 40 if (pla<=mid){ 41 now->rson=form->rson; 42 update(pla,form->lson,now->lson); 43 } else if (pla>mid){ 44 now->lson=form->lson; 45 update(pla,form->rson,now->rson); 46 } 47 } 48 } 49 50 long ask(point* form,point* now,long rank) 51 { 52 long delta_lson; 53 if (now->s==now->e)return now->s; 54 delta_lson=now->lson->sum-form->lson->sum; 55 if (rank<=delta_lson)return ask(form->lson,now->lson,rank); 56 else return ask(form->rson,now->rson,rank-delta_lson); 57 } 58 59 public: 60 void reBuild(long len,long act_times) 61 { 62 leng=len,turn=0; 63 root=new point*[act_times+1]; 64 work(1,len,root[0]); 65 } 66 67 void Update(long pla) 68 { 69 turn++; 70 update(pla,root[turn-1],root[turn]); 71 } 72 73 long Ask(long s,long e,long rank) 74 { 75 if (rank>root[e]->sum-root[s-1]->sum)return -1; 76 else return ask(root[s-1],root[e],rank); 77 } 78 };