【模板】splay
Splay? Mplay?
看她的博客好了blogsdn.net/Clove_unique/article/details/500280?locationNum=1&fps=1
还有一个blogsdn.net/fate_zero_saber/article/details/56496660
最后一个m.blogsdn.net/article/details?id=49978643
反正我也懒得写。
摘录一些：
splay很灵活的，它既可以作为一棵二叉查找树又可以作为一棵区间树，不过不能共存。因此从两方面来说splay。一、splay的rotate，splay操作splay不是特别平衡。不过splay还算是平衡树吧，是有维护平衡的方式的。splay维护平衡的方式就是提根。查询完了某个节点，就把这个节点提根。这样经过证明每次操作是均摊log(n)的。提根就是不停旋转，一次旋转，目标节点总可以被转上去一层，然后最终会到根。单旋和其他平衡树一样。然后注意splay比别的平衡树多了2种双旋，即zigzig和zagzag。为什么呢？因为如果原来splay是一条链（且是一条直链，即左儿子连左儿子一直连下去），把链的尾部提根，如果像别的平衡树一样旋转（自底向上）那么转完了还是一条链，高度没有降低，最坏是O(n)的。对于这种情况，zigzig和zagzag就有用了。这种双旋是这样来的：
如果我们把最下面的点提根，那就要先zig目标节点的父亲，再zig目标节点。（不同于自底向上zig）这样树的高度缩小了。只需要我们多一个维护当前节点的父亲。总结一下，单旋和以前一样，不过要维护父亲。提根(splay)操作，把当前节点转成目标节点的儿子。如果目标节点（一般是0，即转成根；有时是根，即转成根的儿子）不是当前点的父亲的父亲，那么就要双旋。折线形就zigzag，zagzig，直线形就是zigzig，zagzag。如果是，那么就只单旋一次退出循环。
二、平衡树
splay作为平衡树，可以O(logn)完成普通平衡树支持的所有操作。并且由于其支持区间树的特性，很多操作都有两种以上的写法。
插入：与二叉查找树类似。最后要提根。
求前驱：有很多写法了。可以从根向下找（类似于二叉查找树find），找到key[x] < val的就更新。也可以find到目标点，然后提根，在根的左子树里面找最大值。
求后继：同上。
求x的排名：有很多写法了。可以从根向下找，跑到右边子树去了就得+左边的size+根的tot，还可以找到x的前驱，把x的前驱提根，返回此时左边的size+根的tot+1。
求第k大：这个貌似还是像以前一样，从根向下找。
删除x：好像用以前的二叉查找树的方法也可以。。不过还有更简单的，就是找到x的前驱，提根，找到x的后继，提到右儿子。删掉根的右儿子的左儿子，即x。删一段区间也可以这么来，感觉比较像区间树了。
三、可重平衡树
这个和以前一样了，维护一个tot域，然后就可以做了。
没有SBT维护tot域麻烦因为这个sz没有两个意思，删除操作不用以前的，就用提根这样来删代码不怎么复杂。
四、pushup和pushdown
splay的旋转是把一个点向上转，那么需要pushup
pushup主要是在平衡树rotate，splay的时候调用，区间树也是rotate，splay的时候调用，有个build也会用，对某个子区间操作后还要pushup上去更新全区间。
在平衡树中，pushup主要维护一个size
在区间树中，pushup主要维护和别的与儿子有关的参数例如size，min，max，sum，rl（右侧子串长）,ll（左侧子串长），maxl（拼合后整个区间子串长）等等，比较像线段树。
不过一定要注意，splay的父节点也要参与其中。
如线段树维护一个sum：
tree[x].sum=tree[2*x].sum+tree[2*x+1].sum;
splay维护一个sum：
sum[x]=v[ch[x][0]]+v[ch[x][0]]+v[x];
平衡树很少有pushdown。
区间树的pushdown和线段树很像。主要是一个lazy标记。比如rev（翻转标记），delta（区间增加标记）等等。
因为区间翻转，就是左右子树交换，递归下去，继续左右子树交换，直到叶子。但是lazy操作，只把rev标记打在一段区间上，如果要访问这个区间的子区间，即在树上往下走时，再交换左右子树把rev消除掉。delta同理，先打在根上，还有往下走再把根的左右儿子加上delta，把根的delta重置。
因此，pushdown操作主要是发生在从根往下走，走到儿子前pushdown一次。
五、区间树
区间树主要维护一个数列。也可以认为它是一棵二叉查找树，不过key值变成了数列中的下标而非实值。
不过这样不怎么好写。。比如在第x个数后面插入一个y。下标就变了。
因此写区间树就不要想着平衡树，因此，splay就不支持动态区间第k大这种。
区间树还有一个rotateto（x，goal）操作。就是把当前数列中第x个元素提到goal位置。实现就是平衡树的第k大找到节点后splay。再说一遍，这个不需要专门维护下标，只需要size就可以了。
有了这些，区间树支持以下操作：
1.insert(x,y)在第x个数后面插入一个y。就是rotateto(x,0),rotateto(x+1,root)。然后新建一个节点接在根的右儿子的左儿子上面，完了记得pushup，后面不重复提醒了。
2.delete(l,r)删除位置为[l,r]的所有数。就是rotateto(l1,0),rotateto(r+1,root)。然后以根的右儿子的左儿子为根的子树全砍掉。
3.add(l,r)把位置为[l,r]的所有数+1。就是rotateto(l1,0),rotateto(r+1,root)。根的右儿子的左儿子的delta++。
4.reverse(l,r)翻转位置为[l,r]的所有数。就是rotateto(l1,0),rotateto(r+1,root)。根的右儿子的左儿子的rev^=1。
5.min/max/sum(l,r)返回位置为[l,r]的所有数的最小/最大/和。就是rotateto(l1,0),rotateto(r+1,root)。根的右儿子的左儿子的min/max/sum。
洛谷模板题
支持操作：
1.插入x数
2.删除x数(若有多个相同的数，因只删除一个)
3.查询x数的排名(若有多个相同的数，因输出最小的排名)
4.查询排名为x的数
5.求x的前驱(前驱定义为小于x，且最大的数)
6.求x的后继(后继定义为大于x，且最小的数)
——代码
1 #include <cstdio> 2 3 using namespace std; 4 5 const int N = 300005; 6 int n, root, sz; 7 int w[N], cnt[N], size[N], son[N][2], f[N]; 8 9 void clear(int x) 10 13 14 int get(int x) 15 18 19 void update(int x) 20 23 24 void rotate(int x) 25 36 37 void splay(int x) 38 44 45 void insert(int x) 46 54 int now = root, fa = 0; 55 while(1) 56 64 fa = now; 65 now = son[now][x > w[now]]; 66 if(!now) 67 77 } 78 } 79 80 int get_rank(int x) 81 94 ans += cnt[now]; 95 now = son[now][1]; 96 } 97 } 98 } 99 100 int get_kth(int x) 101 114 x = cnt[now]; 115 now = son[now][1]; 116 } 117 } 118 } 119 120 int get_pre() 121 126 127 int get_suc() 128 133 134 void del(int x) 135 143 if(!son[root][0] && !son[root][1]) 144 149 if(!son[root][0] || !son[root][1]) 150 157 oldroot = root; 158 leftbig = get_pre(); 159 splay(leftbig); 160 son[root][1] = son[oldroot][1]; 161 f[son[root][1]] = root; 162 clear(oldroot); 1 update(root); 164 return; 165 } 166 167 int main() 168 183 } 184 return 0; 185 }View Code
Pku模板题
又需要支持区间加，区间翻转，区间平移，指定位置插入一个数，删除一个区间，区间求最小值。
区间平移的话，如果把区间向右平移 t 位，先把 t % 区间长度，防止平移回来，这样就相当于把后面的 t 个数字挪到区间前面，来先把 [ y t + 1, y ] 旋转出来，删除然后插入到 [ x, y t] 区间的前面。就完成了。
——代码
1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 6 #define N 300005 7 #define INF 2100000000 8 9 int n, m, d, root, sz, aa, bb; 10 int a[N], f[N], son[N][2], size[N], Min[N], key[N], add[N], rev[N]; 11 char opt[20]; 12 13 //删除 14 inline void clear(int x) 15 18 19 //判断 x 是父亲的哪个儿子 20 inline int get(int x) 21 24 25 inline void update(int x) 26 32 33 //建树 34 inline int build(int l, int r, int fa) 35 45 46 //标记下放 47 inline void pushdown(int x) 48 57 if(add[x]) 58 64 } 65 66 //查找排名为 x 的数 67 inline int find(int x) 68 81 } 82 } 83 84 //旋转 85 inline void rotate(int x) 86 99 100 //mplay ?? 101 inline void splay(int x,int to) 102 108 109 //区间加 110 inline void Add(int x, int y) 111 123 124 //区间翻转 125 inline void reverse(int x, int y) 126 135 136 //区间向右平移 t 位 137 //先把 t % 区间长度，防止平移回来 138 //这样就相当于把后面的 t 个数字挪到区间前面来 139 //先把 [ y t + 1, y ] 旋转出来 140 //然后插入到 [ x, y t ] 区间的前面 141 inline void revolve(int x, int y, int t) 142 1 164 inline void insert(int x, int y) 165 177 178 inline void del(int x) 179 190 191 inline int get_min(int x, int y) 192 200 201 int main() 202 222 else 223 227 break; 228 } 229 case 'I': scanf("%d %d", &x, &y); insert(x, y); break; 230 case 'D': scanf("%d", &x); del(x); break; 231 case 'M': scanf("%d %d", &x, &y); printf("%d\n", get_min(x, y)); break; 232 } 233 } 234 return 0; 235 }View Code
洛谷模板题（区间翻转）
——代码
1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 6 const int N = 100001; 7 const int INF = 23333333; 8 int n, m, root, sz, aa, bb; 9 int a[N], key[N], f[N], size[N], son[N][2], rev[N]; 10 11 inline void update(int x) 12 15 16 inline int build(int l, int r, int fa) 17 27 28 inline void pushdown(int x) 29 38 } 39 40 inline int find(int x) 41 54 } 55 } 56 57 inline int get(int x) 58 61 62 inline void rotate(int x) 76 77 inline void splay(int x, int to) 78 84 85 inline void reverse(int x, int y) 86 95 96 inline void print(int now) 97 103 104 int main() 105 116 print(root); 117 return 0; 118 }View Code
上一篇：对于2-sat问题的求解
下一篇：[luoguP1198][JSOI2008] 最大数（线段树 || 单调栈）
splay 模板 平衡树