[关闭]
@zzzc18 2017-12-28T17:08:22.000000Z 字数 3173 阅读 1637

可持久化平衡树

可持久化数据结构 Treap


Kirin:可持久化数据结构可以保留历史版本,用新建代替修改。


洛谷模板题

题目描述

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作(对于各个以往的历史版本):

1.插入x数

2.删除x数(若有多个相同的数,因只删除一个,如果没有请忽略该操作)

3.查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数,因输出最小的排名)

4.查询排名为x的数

5.求x的前驱(前驱定义为小于x,且最大的数,如不存在输出-2147483647)

6.求x的后继(后继定义为大于x,且最小的数,如不存在输出2147483647)

和原本平衡树不同的一点是,每一次的任何操作都是基于某一个历史版本,同时生成一个新的版本。(操作3, 4, 5, 6即保持原版本无变化)

每个版本的编号即为操作的序号(版本0即为初始状态,空树)


这里使用FHQ_Treap,因为这种平衡树不进行旋转,并且便于可持久化的理解

其实如果有主席树的基础,理解这个应该不难。
每次操作都要记录一个单独的根,真正有区别的的地方只在split()

  1. int Copy_Node(int pre){
  2. int now=New_Node();
  3. tree[now]=tree[pre];
  4. return now;
  5. }
  6. PAIR split(int k,int val){
  7. PAIR re(0,0);
  8. if(!k)
  9. return re;
  10. int now=Copy_Node(k);
  11. if(val<tree[k].val){
  12. re=split(tree[k].ls,val);
  13. tree[now].ls=re.right;
  14. re.right=now;
  15. }
  16. else{
  17. re=split(tree[k].rs,val);
  18. tree[now].rs=re.left;
  19. re.left=now;
  20. }
  21. update(now);
  22. return re;
  23. }

Copy_Node(int pre)可以新建出一个与 状态相同的节点,并对这个新的节点进行修改,作为当前的版本。

这样一来,访问第 个版本对应的就是以 为根的平衡树。

时间复杂度 ,空间复杂度同样是


  1. #include<ctime>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<algorithm>
  6. using namespace std;
  7. const int MAXN = 500000+9;
  8. int n;
  9. struct T{
  10. int ls,rs;
  11. int RD;
  12. int size,val;
  13. }tree[22000576];
  14. int rt[MAXN];
  15. struct PAIR{
  16. int left,right;
  17. PAIR(int _x=0,int _y=0):left(_x),right(_y){}
  18. };
  19. int New_Node(int val=0){
  20. static int cnt;
  21. cnt++;
  22. tree[cnt].val=val;
  23. tree[cnt].RD=rand();
  24. tree[cnt].size=1;
  25. return cnt;
  26. }
  27. int Copy_Node(int pre){
  28. int now=New_Node();
  29. tree[now]=tree[pre];
  30. return now;
  31. }
  32. void update(int x){
  33. tree[x].size=tree[tree[x].ls].size+tree[tree[x].rs].size+1;
  34. }
  35. PAIR split(int k,int val){
  36. PAIR re(0,0);
  37. if(!k)
  38. return re;
  39. int now=Copy_Node(k);
  40. if(val<tree[k].val){
  41. re=split(tree[k].ls,val);
  42. tree[now].ls=re.right;
  43. re.right=now;
  44. }
  45. else{
  46. re=split(tree[k].rs,val);
  47. tree[now].rs=re.left;
  48. re.left=now;
  49. }
  50. update(now);
  51. return re;
  52. }
  53. int merge(int x,int y){
  54. if(x==0 || y==0)
  55. return x+y;
  56. if(tree[x].RD<tree[y].RD){
  57. tree[x].rs=merge(tree[x].rs,y);
  58. update(x);
  59. return x;
  60. }
  61. else{
  62. tree[y].ls=merge(x,tree[y].ls);
  63. update(y);
  64. return y;
  65. }
  66. }
  67. void insert(int pre,int now,int val){
  68. PAIR rt1=split(rt[pre],val);
  69. rt[now]=merge(rt1.left,merge(New_Node(val),rt1.right));
  70. }
  71. void del(int pre,int now,int val){
  72. PAIR rt1=split(rt[pre],val-1);
  73. PAIR rt2=split(rt1.right,val);
  74. rt2.left=merge(tree[rt2.left].ls,tree[rt2.left].rs);
  75. rt[now]=merge(rt1.left,merge(rt2.left,rt2.right));
  76. }
  77. int n2r(int pre,int now,int val){
  78. PAIR rt1=split(rt[pre],val-1);
  79. int re=tree[rt1.left].size;//由于有-INF,不再+1
  80. rt[now]=merge(rt1.left,rt1.right);
  81. return re;
  82. }
  83. int r2n(int now,int val){
  84. int k=now;
  85. while(val<=tree[tree[k].ls].size || val>tree[tree[k].ls].size+1){
  86. if(val<=tree[tree[k].ls].size)
  87. k=tree[k].ls;
  88. else{
  89. val-=tree[tree[k].ls].size+1;
  90. k=tree[k].rs;
  91. }
  92. }
  93. return tree[k].val;
  94. }
  95. int r2n(int pre,int now,int val){
  96. rt[now]=rt[pre];
  97. return r2n(rt[now],val+1);
  98. }
  99. int pred(int pre,int now,int val){
  100. PAIR rt1=split(rt[pre],val-1);
  101. int re=r2n(rt1.left,tree[rt1.left].size);
  102. rt[now]=merge(rt1.left,rt1.right);
  103. return re;
  104. }
  105. int succ(int pre,int now,int val){
  106. PAIR rt1=split(rt[pre],val);
  107. int re=r2n(rt1.right,1);
  108. rt[now]=merge(rt1.left,rt1.right);
  109. return re;
  110. }
  111. int main(){
  112. srand(time(0));
  113. insert(0,0,-2147483647);
  114. insert(0,0,2147483647);
  115. scanf("%d",&n);
  116. for(int i=1;i<=n;i++){
  117. int v,opt,x;
  118. scanf("%d%d%d",&v,&opt,&x);
  119. if(opt==1)
  120. insert(v,i,x);
  121. else if(opt==2)
  122. del(v,i,x);
  123. else if(opt==3)
  124. printf("%d\n",n2r(v,i,x));
  125. else if(opt==4)
  126. printf("%d\n",r2n(v,i,x));
  127. else if(opt==5)
  128. printf("%d\n",pred(v,i,x));
  129. else
  130. printf("%d\n",succ(v,i,x));
  131. }
  132. return 0;
  133. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注