Splay学习笔记

Splay是一个二叉平衡树，可以维护序列，支持在其中插入和删除。

关键操作：rotate，即旋转，可以更换子树的根。分为左旋和右旋。splay通过不断地将新加入的节点旋转到根来保证期望深度为log。经过发展，rotate函数在代码内已经非常的简洁，将左旋和右旋合并为一个函数（关键在于用k存储x为y的左儿子还是右儿子，运用异或表示“另一个儿子”）。rotate更新父母和孩子的顺序：zy->zx,xa->ya,yx->xy，要牢记。旋转的过程中平衡树的中序遍历是不变的。

splay函数是核心操作。splay(x,k)表示把x旋转到k的下面。k一般是0或者根节点。splay过程中关注x的父亲（y）和y的父亲（z）。如果xyz在一条直线，则先旋转y再转x。否则转两次x。不这样做会被构造数据卡掉。

splay的节点可以维护标记。像线段树那样下传即可。pushdown在递归前必须写。pushup在函数结尾写。注意pushup的顺序。该pushdown的时候一定要pushdown。

insert的时候，初始时要满足堆的性质。如果题目中的操作会改变堆的性质，可以随便插。如果不会改变。如《郁闷的收纳员》，不管怎样都会满足堆的性质，还会利用到它，则要保证插入顺序。所以尽量保证堆的性质。

getk时先pushdown！注意跳右儿子时先改k再改nw。

插入区间，先找到插入位置的后继，然后将插入位置旋转到根，后继旋转到根下面，左儿子便是空的，可以直接插入你构造的区间的二叉树。删除区间同理，不过要找到两端的前驱后继。为了防止越界，可以再0、n+1的位置设置“哨兵”，值为极值。不过处理的时候要特别留意它们。