平衡树 - FHQ 学习笔记

平衡树 - FHQ 学习笔记

主要参考万万没想到 的 FHQ-Treap学习笔记。

本片文章的姊妹篇：平衡树 - Splay 学习笔记。

感觉完全不会平衡树，又重新学习了一遍 FHQ，一口气把常见套路都学完了。

一、大致内容及分类

FHQ(???)，全称非旋转 Treap，是一种可以用于维护按权值、排名分裂的数据结构。它相比与 Splay 虽然常数较大，但是实现起来代码难度相对容易，而且由于它非旋的特点，也可以用来实现可持久化。

既然叫做非旋 Treap，它兼有 Treap 的特点又有非旋转独特的优势。

• 从 Treap 角度看，他们同样都是依赖修正值 rnd 是随机的，用将他们按照 rnd 形成一个小根堆。与 Treap 相同，它也满足笛卡尔树的性质，它的中序遍历和它的插入顺序相同，即 $1$ 到 $n$ 的序列。
• 从非旋角度看，FHQ 直接通过 split 和 merge 操作实现添加、删除元素，不用再树上旋转了。

根据不同题目要求，将平衡树分为序列平衡树和权值平衡树。

• 序列平衡树的中序遍历为每个元素在序列中的下标，权值为每个元素具体的值，常见题型为区间翻转等。
• 权值平衡树的中序遍历是所有元素从小到大排序，即按照中序遍历提取所有元素后元素权值递增，常见操作为第 $k$ 大等。

如果毒瘤出题人同时综合了以上两种操作，即区间翻转 $+$ 区间第 $k$ 大，应该怎么做呢？好吧，如果真是这样，这篇文章可能不能够帮到你，直接上一个根号做法！

二、基本操作

FHQ 的核心操作就是 split 出操作区间，操作完后 merge 回去。

下边讲解中默认的平衡树类型为权值平衡树，序列平衡树其实是将某些 $val$ 改为了 $siz$。

分裂 split

无论是按照排名还是权值分裂，他们都是将原树分为左右两半，可以利用中序遍历的性质进行分裂。

具体操作时，我们新建两个临时变量 $x,y$ 分别表示分裂出来的左边、右边的那颗平衡树。

如果我们遇到一个应该属于 $x$ 树的节点，就将这个点以及这个点的左子树加入 $x$ 树中，并递归分裂右子树；如果遇到属于 $y$ 的，就将这个点与它的右子树加入 $y$ 树中，并递归分裂左子树。

需要注意到是，如果使用序列平衡树，下面和 $k$ 的大小判断应该变为 $ls.siz+1\le k$。

$\bigstar\texttt{Attention}$