[模板] FHQ Treap 与可持久化平衡树
$\mathrm{FHQ} \ \mathrm{Treap}$ 是一类基于 $\mathrm{Split}$ 和 $\mathrm{Merge}$ 操作的平衡树,不需要旋转的特性是可持久化平衡树的基础
$\mathrm{FHQ} \ \mathrm{Treap}$ 是一类基于 $\mathrm{Split}$ 和 $\mathrm{Merge}$ 操作的平衡树,不需要旋转的特性是可持久化平衡树的基础
替罪羊树(重量平衡树)和 Treap (树堆)也是两种常用的平衡树,分别基于平衡因子和随机附加域来保证子树的平衡。
一道线段树套平衡树的模板题,支持在区间中完成平衡树的相关功能,本题可以在 $O(log^2 n)$ 的时间内进行区间单点修改,查询某一个区间内的前驱,后继,排名,并通过二分的方法,在 $O(log^3 n)$ 的时间内查询区间 $k$ 小值。
$Splay$ 是一种二叉排序树,因此满足二叉排序树的所有性质。支持在 $O(l […]