treap怎样跑得更快

· · 个人记录

点开陈立杰13年的集训队论文，发现treap具有性质：每次新插入元素在treap中的子树大小为 O(\log{n})。

如果使用非旋treap作为名次树，insert/delete的时候可以在原树上走到需要插入的位置，再从这里开始merge/split，merge/split部分的期望复杂度为 O(\log{\log{n}})（其实鉴于对数函数的凹凸性问题，E(\log{x}) 和 \log{E(x)} 并不能画等号，这里冷静一下是可以分析到 O(1) 的），而 O(\log{n}) 部分的常数主要是在树上遍历，是静态操作，常数很小。

然而一般不会使用平衡树仅仅作为名次树。

论treap的正确使用姿势