Treap

treap 果然是一条好汉。

普通平衡树？treap 基本功能。fanhq 式的写法超级漂亮，基本不会写错（注意大于小于号即可）。原论文中说了 treap 的插入期望旋转两次，也就是说 insert 的时调用的 split 常数会很小。

关于权值的问题，我习惯搞个大根堆，因为懒得给 null 赋初始权值了。

splay 的拿手好戏，序列操作？由于 treap 支持 split/merge ，所以毫无压力。而且由于普通的 insert/erase 都涉及 split/merge 了，所以这是必备的。换句话说，treap 支持序列操作和 splay 一样天然。

另外，treap 还可以原生支持持久化，只需每次修改一个点时新建一个点代替就好了。一个小改动就是动态 weight ，因为 weight 不能持久化。内存占用什么的都是浮云。splay 要想持久化的话感觉比较囧，老教授的方法是多次（ \(O(\log n)\) 次） deep-splay，即把最深的点旋上来。

根据 CLJ 的论文，我们可以知道 treap 还是重量平衡的。fanhq 的写法中 split/merge 需要完完整整重构树，但是复杂度分析类似。（代码量？都是浮云啦……）

目前就 finger search 不支持了？

代码量什么的，感觉和 splay 差不多了。