[关闭]
@Bei-S 2019-01-14T00:15:02.000000Z 字数 1469 阅读 350

可持久化数据结构

数据结构


起风了,唯有努力生存。
随风逝,不带一丝伤痕。


有些时候我们会遇到一些奇奇怪怪的题目,例如需要你记录下一个数组的历史版本。
这时候我们怎么办呢?暴力所有开m个线段树/数组?的空间估计多半吃不消
这时候我们就要引入一个神奇的数据解构 ——— 可持久化线段树(主席树)。

主席树主要可以用于处理区间第K大之类的问题。

而主席树的实质呢就是对每个前缀([1,1],[1,2],[1,3]...)建立一颗权值线段树,每次更改时如果左(右)儿子没变,我们直接指向他上一颗树的儿子即可,同时我们记录每颗权值线段树的根节点和左右儿子。这样每次我们最多更改个节点,空间降为
我们可以看出这个主席树是具有可减性的。例如我们要求区间[l,r]的第K大时,我们只需用第r颗线段树减去第l-1颗线段树即可。
当然代码中我们肯定不是直接减啦,我们只需每次往下传递节点,统计答案时直接用即可,这里r和l-1指的是这两颗权值线段树上的节点,不一定是L-1,R哦。

那么可持久化数组就可以用主席树轻松实现了,因为每次相当于更改一个节点,即单点修改。

基于此,我们就可以愉快地实现可持久化冰碴鸡了(@菜XX)

至于可持久化平衡树么。。。等我学了FHQ Treap再说吧
Code:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define mid ((l+r)>>1)
  4. const int N=2e5+7;
  5. int n,m,q,tot;
  6. int a[N],b[N];
  7. int rt[N],sum[N*20],ls[N*20],rs[N*20];
  8. inline int build(int l,int r){
  9. int s=++tot;
  10. if(l<r){
  11. ls[s]=build(l,mid);
  12. rs[s]=build(mid+1,r);
  13. }
  14. return s;
  15. }
  16. inline int update(int pre,int l,int r,int x){
  17. int s=++tot;
  18. ls[s]=ls[pre];rs[s]=rs[pre];sum[s]=sum[pre]+1;
  19. if(l<r){
  20. if(x<=mid) ls[s]=update(ls[pre],l,mid,x);
  21. else rs[s]=update(rs[pre],mid+1,r,x);
  22. }
  23. return s;
  24. }
  25. inline int sa(int u,int v,int l,int r,int k){
  26. if(l==r) return l;
  27. int x=sum[ls[v]]-sum[ls[u]];
  28. if(x>=k) return sa(ls[u],ls[v],l,mid,k);
  29. else return sa(rs[u],rs[v],mid+1,r,k-x);
  30. }
  31. int main(){
  32. scanf("%d%d",&n,&q);
  33. for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
  34. sort(b+1,b+1+n);
  35. int m=unique(b+1,b+1+n)-b-1;
  36. rt[0]=build(1,m);
  37. for(int i=1;i<=n;i++){
  38. a[i]=lower_bound(b+1,b+1+m,a[i])-b;
  39. rt[i]=update(rt[i-1],1,m,a[i]);
  40. }
  41. for(int i=1;i<=q;i++){
  42. int x,y,z;
  43. scanf("%d%d%d",&x,&y,&z);
  44. printf("%d\n",b[sa(rt[x-1],rt[y],1,m,z)]);
  45. }
  46. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注