1. treap
- 堆的性质
treap = tree + heap
也就是 treap 是具有堆性质的平衡二叉树(BST), 而堆性质的维护就靠一个随机值和旋转操作. 可以是小根堆也可以是大根堆.
用 r 数组(random)保存随机值, 那么在插入结点时需要维护堆性质(这里是大根堆)
ch[o][0] 、ch[o][1] 分别表示 结点o 的左儿子和右儿子.
自己定义宏 :#define lc ch[o][0]#define rc ch[o][1]if(r[ch[o][d]] > r[o]) rotate(o, d^1); // rotate见下方
- 左旋和右旋 有太多的相似处, 可以用一个带旋转方向参数的 rotate 操作来完成
d = 0 表示左旋, d = 1 表示右旋.void rotate(int& o, int d) { int k = ch[o][d^1]; ch[o][d^1] = ch[k][d]; ch[k][d] = o; update(o); update(k); o = k; }
删除
- 首先得找到要删除的结点
如果该结点只有一个左儿子或只有一个右儿子, 直接将它把要删除的结点取代.
if(lc * rc == 0) o = lc + rc;否则就考虑堆性质的维护
int d2 = tr[t.ch[0]].r < tr[t.ch[1]].r ? 1 : 0; rotate(o, d2); remove(o, x);
- 查询
- 查询第 k 大
如果要查询的结点在当前结点的右儿子上, 那么继续查询右儿子的第k-s[lc]-1大.- 查询某结点排名
如果要查询的结点在当前结点的右儿子上, 那么排名应该增加s[lc]+1.
2. splay
- 和 treap 比较起来, splay 多的就是伸展(splay)操作.
关于伸展操作
两种实现方式 : 自顶向下和自底向上.
自底向上的 splay 我是参考的 HZWER, 需要使用fa数组记录当前结点的父结点. 比较方便的是可以直接通过这个fa数组发现从一个结点走到任意已知结点的路径. 于是就诞生了自底向上的splay. 正因为这种特性, 这种伸展方式可以适应任何题目.void rotate(int& px, int& x, int d) { int t = ch[x][d]; ch[x][d] = px; ch[px][d^1] = t; p[x] = p[px]; p[px] = x; p[t] = px; update(px); update(x); px = x; } void splay(int x, int& k) { while(x != k) { int y = p[x], z = p[y]; int d = ch[y][0] == x ? 0 : 1; int d2 = ch[z][0] == y ? 0 : 1; if(y != k) rotate(ch[z][d2], x, d^1); else rotate(k, x, d^1); } }自顶向下的 splay 可以看《训练指南》, 刘汝佳的代码. 比较简洁高效. 我是把指针改成了数组, 不习惯指针的写法, 主要是不知道怎么调试.
void splay(int& o, int k) { int d = cmp(o, k); if(d == -1) return; if(d == 1) k -= s[lc] + 1; int p = ch[o][d]; int d2 = cmp(p, k); int k2 = (d2 == 0) ? k : k-s[ch[p][0]]-1; if(d2 != -1) { splay(ch[p][d2], k2); if(d == d2) rotate(o, d^1); else rotate(ch[o][d], d); } rotate(o, d^1); }自顶向下就需要知道你想 splay 的结点的排名. 那么有的题目比如 书架 那个题, 直接告诉你哪个结点编号, 但它是第几个结点不知道, 这样就只能用第一种自底向上的splay了.
- 另外splay可以一次旋转两回也可以旋转一回, 即单旋和双旋. 单旋的方法比较简单, 整个过程相当于先找到第 k 个结点, 再递归自底向上旋转到目标结点. 不过在有些情况会退化成一条链O(n). 转两回的参考《训练指南》.
void splay(int& o, int k) { int d = cmp(o, k); if(d == -1) return; if(d == 1) k -= s[lc] + 1; splay(ch[o][d], k); rotate(o, d^1); }
其他操作和 treap 差不多, 但 splay 支持很多区间操作
- 得到一段区间, 把它移动到一个固定结点.
都采用自顶向下的splay
注意这里在首部和末尾都添加一个虚拟结点防止溢出.// 移动到根结点右儿子的左儿子 void getInterval(int o, int L, int R) { splay(o, L); splay(rc, R - s[lc] - 1); }// 移动到根结点左儿子的右儿子 void getInterval(int o, int L, int R) { splay(o, L); splay(o, R + 2); }
- 第二种方法只适用于单旋splay
- 有了这个获取区间的题目, 就可以完成很多区间的题目, 比如区间修改、区间翻转、区间标记之类的.