这是新坑……
同时开了KDT和LCT的坑【不知道的同学等下就知道了】
0x00
绝大多数的平衡树维持平衡是通过旋转操作
Merge_Split_Treap 是通过分裂合并维护堆的性质保持理论上的平衡
今天讲的替罪羊树是用来暴力维护子节点重量平衡的
0x01
某教程的传送门
另一个教程的传送门
这两个教程里面的说明都很有意思，可以看看
0x02
替罪羊树最神奇的地方就在于他的暴力重建
而且这个暴力重建是有时间复杂度保证的【势能分析那一套理论不是很懂，需要证明的可以去翻翻之前陈老师的论文】
保证每种平衡树的操作的时间复杂度在\(O(logN)\)的范围
替罪羊树还有一个小技巧
就是拍扁重建法
重建的时候先dfs把所有数放进一个数组，重建每一层递归都把mid拿出来当father即可
时间复杂度是O(size)的
最后讲的是替罪羊树的删除
因为这个树是没有旋转的
不能把它某个节点旋转到叶子然后把叶子节点删掉
所以用的是惰性删除
在删除的时候 打一个删除标记 表示“这个点被删除了 以后查询的时候直接跳过”
若一个子树内的惰性节点超出了某个范围【比如\(size*0.45\)】直接暴力重建
注意：
重建的时候带有删除标记的节点不能入数组
重建的两个条件
1.子树深度大于某个阈值 或 子树大小大于阈值 【实际上是等价的？】
2.子树内带有删除标记的节点大于阈值
0x03
代码
这份过了编译【就是不保证完全正确但是思路是对的】
状态好了来认真写一份……
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 |
#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <cstdlib> #include <cmath> #define ll long long #define INF 1000000000 #define For(i,a,b) for(int i=a;i<=b;++i) #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; C=1; cc=getchar(); while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } #undef p using namespace std; #define N 100010 const double alpha=0.65; const double beta=0.5; struct node { int c[2],fa,siz,cnt; int inf,val; bool del; node() { c[0]=c[1]=fa=cnt=0; siz=1; del=false; } // infor. }pool[N]; int pcnt,last,root; #define FA pool[x].fa #define Lc pool[x].c[0] #define Rc pool[x].c[1] #define SIZ pool[x].siz #define CNT pool[x].cnt #define DEL pool[x].del #define VAL pool[x].val int Bin[N],tot; int new_() { static int ret; if(!tot) return ++pcnt; ret=Bin[--tot]; pool[ret]=node(); return ret; } void PushUP(int x) { SIZ=pool[Lc].siz+pool[Rc].siz+1; CNT=pool[Lc].cnt+pool[Rc].cnt+(DEL?1:0); } int Arr[N],_; void flatten(int x) { if(!x) return; flatten(Lc); if(!DEL)Arr[++_]=x; else Bin[++tot]=x; flatten(Rc); } int build(int l,int r) { if(l==r) { int x=Arr[l]; pool[x].c[0]=pool[x].c[1]=0; pool[x].siz=1; return Arr[l]; } int mid=(l+r)>>1,x=Arr[mid]; if(mid-1>=l)Lc=build(l,mid-1),pool[Lc].fa=x; Rc=build(mid+1,r),pool[Rc].fa=x; PushUP(x); return x; } void rebuild(int x) { _=0; flatten(x); if(x==root)root=build(1,_); else { int node=FA; pool[node].c[0]==x?pool[node].c[0]=build(1,_):pool[node].c[1]=build(1,_); } } void insert(int &x,int val,int fa) { if(!x) { x=new_(); FA=fa; VAL=val; return; } if(val==VAL&&!DEL) { pool[x].inf++; return; } insert(val<VAL?Lc:Rc,val,x); PushUP(x); if(pool[val<VAL?Lc:Rc].siz>pool[x].siz*alpha||pool[x].cnt>pool[x].siz*beta) last=x; } void erase(int x,int val) { if(VAL==val) { if(!--pool[x].inf) { pool[x].del=true; PushUP(x); } return; } if(VAL>val) erase(Lc,val); else erase(Rc,val); PushUP(x); if(pool[val<VAL?Lc:Rc].siz>pool[x].siz*alpha||pool[x].cnt>pool[x].siz*beta) last=x; } int main() { int m; for(read(m);m;m--) { } /* last=0; insert(root,val,0); if(last) rebuild(last); */ /* last=0; erase(root,val); if(last) rebuild(last); */ return 0; } |