Treap

参考资料

• Treap - OI Wiki

简介

Treap（Tree + Heap）给每个节点附一个随机优先级，使其按键值满足二叉搜索树性质、按优先级满足堆性质。随机优先级让期望树高为 $O(\log n)$，从而支持 $O(\log n)$ 的插入、删除、排名、前驱后继等操作。

竞赛中常用 无旋 Treap（FHQ Treap）：只用 split（按键或按大小分裂）与 merge（合并两棵相对有序的树）两个操作即可实现全部功能，代码简短，且天然支持可持久化与区间翻转。

例题

洛谷 P3369 【模板】普通平衡树

你需要写一种数据结构，来维护一些数，并且提供以下操作：

1. 插入一个数 $x$。
2. 删除一个数 $x$（若有多个相同的数，应只删除一个）。
3. 定义排名为比当前数小的数的个数 $+1$。查询 $x$ 的排名。
4. 查询数据结构中排名为 $x$ 的数。
5. 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。
6. 求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。