Splay

　0.rotate()左旋右旋。找点规律可以写一起;

　　splay()利用rotate()把一个节点转到目标点的儿子处;

　　find()找到一个节点并把它转到根，没有这个节点那就可能是把他的前驱或者后继转上来;

　　nxt()利用find()找前驱、后继，把x转上来之后，暴力跳子树就可以了;

　　insert()向下查找时要同时记录父节点;

　　pop()利用nxt()找到前驱后继，然后把前驱旋到根，后继旋到前驱儿子处，这样x就在后继的右儿子处且x没有儿子;
　
　　kth()注意是<=不是<;

　　rnk()直接find()然后取\(sum[ch[rt][0]]+1\)即可;

　　区间修改问题可以把l-1旋到根，r+1旋到根的儿子，那么区间\([l,r]\)就在节点r+1的左子树，打个reverse标记即可。等询问到这个节点时，先下传标记。修改后update，进入子树前pushdown，能splay就splay.

　1.更新节点可以直接splay()，不需要做两次update()，因为rotate()过程中会update()。（除了删除一个节点时，即cnt=0时，因为这个时候这个节点已经从树上删去，不可能从他开始splay）。
　2.操作完能splay()就尽量splay()。
　3.开局insert()inf和-inf两个哨兵节点，以防要查找的值比树上值都小/大。同时要注意rnk()和kth()要相应做微调。
　4.find()的while做完后p不能为0（因为最后要splay()，如果是0做splay()会把rt也置为0），而insert里的可以为0（当p为0时会新增一个节点，p就不为0了）。

fhq_treap

　0.Treap是随机附加域满足堆(例如小根堆)性质的二叉搜索树。

　　split有按权值分裂(权值小于等于k的在左树)和按排名分裂(就是前k大在左树)，按权值用的比较多。讨论一下当前节点的情况看分到左树还是右树然后递归就可以了;

　　merge假设x的权值是小于y的，那么其左右的相对位置已经符合BST性质，只需考虑满足堆性质，讨论一下x和y的key值大小决定谁做根(小根堆就key小的做根)，然后递归处理;

　　insert因为treap中元素是可重的，所以直接按权值x把treap分裂，然后加入一个新点再merge起来;

　　pop先按权值x分裂，再把左树按权值x-1分裂，这样得到的新的右树的点权值都是x。把新的右树根的两个儿子merge起来，就相当于把根pop掉了，然后再把三堆merge成一个treap;

　　rnk按权值x-1分裂，答案就是左树大小+1;

　　kth和splay一样实现就好了。刚开始想着用按排名分裂搞搞，但常数反而还不如暴力跳优秀;

　　pre按权值x-1分裂，再kth查询左树最大的就可以了(排名为左树大小的那个);

　　suf按权值x分裂，再kth查询右树最小的就可以了(排名为1的)。

　1.任何操作做完都要merge回来，保证时刻只有一个treap。

　2.不需要建哨兵节点。splay要建的原因是pop的时候要访问前驱和后继。

　3.还是一样的，修改后update，进入子树前pushdown，修改完千万别忘update！！！

例题

Luogu3369 【模板】普通平衡树

Link
板子题。

Luogu3391 【模板】文艺平衡树

Link
一旦进入子树就pushdown。
注意这两道题splay都需要建立哨兵节点。

平衡树初探

原文：https://www.cnblogs.com/fruitea/p/12018651.html