FHQ Treap 学习笔记

本文章最后更新日期为:2021-09-12

FHQ Treap 是什么

要明白这个问题,我们首先得明白 Treap 是什么。

树堆(Treap),是有一个随机附加域满足堆的性质的二叉搜索树,其结构相当于以随机数据插入的二叉搜索树。相对于其他的平衡二叉搜索树,Treap 的特点是实现简单,且能基本实现随机平衡的结构。(摘录自百度百科)

那就十分奇怪了,Treap 之前的 FHQ 又是什么意思呢?
注意:FHQ Treap 是 FHQ 神犇发明的!

FHQ Treap 相比普通的 Treap 的不同点:

  • 不需要进行旋转
  • 可以进行可持久化
  • 易于理解
  • 但常数比普通的 Treap 大

FHQ Treap 用来干什么

FHQ Treap 支持以下操作:

  • 插入 xx
  • 删除一个 xx
  • 查询排名为 kk 的数
  • 查询 xx 的排名
  • 查询 xx 的前驱(最大的小于 xx 的数)
  • 查询 xx 的后继(最小的大于 xx 的数)
  • 区间翻转(本文暂时不涉及)
  • 可持久化(本文暂时不涉及)

普通 Treap 可以干的活 FHQ Treap 也可以!

FHQ Treap 的主要思想

组成部分

节点、节点数值、节点左右儿子、随机权值、子树大小、目前节点总数量、FHQ Treap 的根节点。

1
node, val[node], son[node][0], son[node][1], rnd[node], treeSize[node], cnt, root

更新

一般的更新为更新节点的子树的大小:

sizenodesizenode.leftSon+sizenode.rightSon+1size_{node} \gets size_{node.leftSon} + size_{node.rightSon} + 1

将节点 node 的左儿子的子树大小与右儿子的子树大小相加之后再增加 11(还有 node 自己)之后就是 node 子树的大小了。

1
2
3
inline void update(int node) {
treeSize[node] = treeSize[son[node][0]] + treeSize[son[node][1]] + 1;
}

分裂

根据数值进行分裂(常用)

void split(int node, int y, int &left, int &right) 为数值分裂函数。
其中 node 表示需要分裂的 Treap 的根,y 为分裂的数值,left 为左边部分(左子树)的根,right 为右边部分(右子树)的根。
将 Treap 分为两部分,左子树 valnodeyval_{node} \leqslant y,右子树 valnode>yval_{node} > y

为了进行数值分裂,需要进行以下步骤:

  1. 判断 node 是否存在,若不存在则返回(return)。
  2. 如果 node 的值小于等于 yy 则将 node 分配到左子树,并且以 node 作为左子树的根,由于左子树的最大值小于等于根,所以把 node 的右子树再次进行分裂(将小于等于 yy 的分裂到左子树的根(left)的左儿子(son[left][0]),而大于 yy 的仍然分裂到右子树 right。想一想,为什么?)。

原因

由于我们在构建 Treap(马上就会讲到)时将节点根据平衡树原则进行分配,所以节点 node左儿子的值小于等于本身右儿子的值大于等于本身。所以可以确定 node 的左儿子及左儿子的子树中所有的值都小于等于 yy ,但无法确定 node 的右儿子中是否存在值大于 yy 的情况,于是对右儿子 son[node][1] 进行分裂。分裂时由于先前已经分出左子树,所以我们只需要将右子树中小于等于 yy 的分配到左子树根节点的右儿子(因为右子树的值毕竟大于 node,所以不能分配到左子树根节点 left 的左儿子,我们已经把 node 赋值给了 left,所以此时 nodeleft 应该是相等的),而大于 yy 的部分分配到先前的 right 右子树上去即可。

  1. 如果 node 的值大于y 则将 node 分配到右子树,并且以 node 作为右子树,由于右子树的最小值小于根,所以把左子树再次进行分裂(原因同上)。
  2. 更新 node

进行数值分裂之后 left 就代表整棵 Treap 中小于等于 yy 的树的根节点,而 right 就代表整棵 Treap 中大于 yy 的树的根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void split(int node, int y, int &left, int &right) {
if (!node) {
left = 0;
right = 0;
return;
}

if (num[node] <= y) {
left = node;
split(son[node][1], y, son[left][1], right);
} else {
right = node;
split(son[node][0], y, left, son[right][0]);
}

update(node);
}

根据子树大小进行分裂

同样的,void split(int node, int k, int &left, int &right) 为子树大小分裂函数(好像就一个字母的区别)。
函数中的 k 代表根据前 kk 个来进行分裂,将前 kk 个分裂进入 left,其他的分入 right

步骤:

  1. 同样判断 node 是否存在。
  2. 如果 node 的左子树大小小于 kk 就将 node 设为左子树的根节点,对 node 的右子树进行分裂。
  3. 否则将 node 设为右子树的根节点,对 node 的左子树进行分裂。

为什么 kk 会变化?

我们分裂左子树的时候由于整个左子树的大小小于 kk,所以将整个左子树分到左边部分,而这时候左边部分的 treeSize 仍然小于 kk,于是我们需要到右子树进行分裂,而所需要的数量为 ksizenode.leftSon1k-size_{node.leftSon}-1,想一想为什么还需要再减 11 呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void split(int node, int k, int &left, int &right) {
if (!node) {
left = 0;
right = 0;
return;
}

if (treeSize[son[node][0]] < k) {
left = node;
split(son[node][1], k - treeSize[son[node][0]] - 1, son[left][1], right);
} else {
right = node;
split(son[node][0], k, left, son[right][0]);
}

update(node);
}

合并

从名字上就可以知道合并是将分裂出来的两颗子树在合并回去。

步骤:

  1. 仍然是判断两棵树是否存在。
  2. 如果 x 的随机权值小于 y 的随即权值就将 y 合并到 x 的右子树去。
  3. 否则将 x 合并到 y 的左子树去。
  4. 记得更新 xy

为什么要基于随机权值?

首先需要明白的是,在 Treap 中,左儿子的值一定小于等于本身的值,而合并时的随机权值决定的只是整个 Treap 的结构。

为了保证整棵树趋于平衡(不然也不会叫平衡树了),我们就需要对每一个节点赋予一定的权值,这个权值与本身的值并没有必然联系,但可以保证我们整个 Treap 趋于平衡。这也是我们不在 merge 中直接随机分配的原因。

为了使用方便,我们将合并起来的两棵树的根节点作为合并函数的返回值(优点大大的有)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int merge(int x, int y) {
if (!x || !y) {
return x ^ y; // 返回 x 和 y 其中不为 0 的数
}
if (rnd[x] < rnd[y]) {
son[x][1] = merge(son[x][1], y);
update(x);
return x;
} else {
son[y][0] = merge(x, son[y][0]);
update(y);
return y;
}
}

获取随机数

喂喂喂!现在都什么年代了还在 srand 呢?新神器来了!C++11 中隆重登场的 random 库解君愁(如果不能用 C++11 就当我没说。。。)

1
2
3
4
5
#include <random>

std::mt19937 rng(std::random_device{}());

rnd[node] = rng() % std::numeric_limits<int>::max();

至于为什么要取模,因为曾经被溢出支配。

其他的操作

有了以上的几种函数,我们就可以进行一些其他的操作了。

插入

插入一个新的数 xx 需要两个函数:创建节点 x 和将 x 合并进入 Treap 中。

创建节点十分的简单:

1
2
3
4
5
6
int addNode(int x) {
num[++cnt] = x;
treeSize[cnt] = 1;
rnd[cnt] = rng() % std::numeric_limits<int>::max();
return cnt;
}

将节点合并进入 Treap 也十分简单:

1
2
3
4
5
void insert(int x) {
int left, right;
split(root, x, left, right);
root = merge(merge(left, addNode(x)), right);
}

你是不是一下就明白其中的道理了?那么这个 root 又是什么东西?没错,正是整棵 Treap 的根节点!

删除

对于您这种神犇来说肯定不在话下:

1
2
3
4
5
6
7
void erase(int x) {
int left, right, leftRight;
split(root, x, left, right);
split(left, x - 1, left, leftRight);
leftRight = merge(son[leftRight][0], son[leftRight][1]);
root = merge(merge(left, leftRight), right);
}

其实就是合并的时候不把 x 合并就好了。

查询 x 的排名

为了获取 xx 的排名,我们需要将整棵 Treap 分为两部分,左子树小于等于 x1x - 1,右子树自然就是大于等于 xx 的了。
之后我们获取左子树的大小再 +1+1 就是 xx 在整个 Treap 中的排名了!

为什么不从 xx 进行分裂?

如果分裂时选择将小于等于 xx 的分到左子树中,那么如果存在多个 xx 的情况下我们就无法知道第一个 xx 的排名,同时排名也定义为比 xx 小的数字个数加 11,那么我们就可以直接按照定义来进行分裂。

1
2
3
4
5
6
7
int get_x_k_th(int x) {
int left, right, kth;
split(root, x - 1, left, right);
kth = treeSize[left] + 1;
root = merge(left, right);
return kth;
}

如果 Treap 里的数各不相同,那么就可以联合数值分裂来打败子树大小分裂了!

查询排名为 k 的数

几乎同样的步骤:

  1. 先看看 node 的左子树的大小,如果为 k1k-1 那么 node 就是我们要找的数。
  2. 如果左子树的大小大于等于 kk, 那么就在左子树中寻找。
  3. 如果左子树的大小小于 kk,就在右子树中寻找 ksizenode.leftSon1k-size_{node.leftSon}-1 名。

为什么 kk 又变了?

当左子树的大小小于 kk 时,说明我们需要找的数在右子树中,而我们需要在右子树中查找的排名已经不是 kk 了,需要去掉左子树以及 node

1
2
3
4
5
6
7
8
9
int k_th(int node, int k) {
if (treeSize[son[node][0]] + 1 == k) {
return num[node];
} else if (treeSize[son[node][0]] >= k) {
return k_th(son[node][0], k);
} else {
return k_th(son[node][1], k - treeSize[son[node][0]] - 1);
}
}

前驱

1
2
3
4
5
6
7
int get_precursor(int x) {
int left, right, precursor;
split(root, x - 1, left, right);
precursor = k_th(left, treeSize[left]);
root = merge(left, right);
return precursor;
}

后继

1
2
3
4
5
6
7
int get_successor(int x) {
int left, right, successor;
split(root, x, left, right);
successor = k_th(right, 1);
root = merge(left, right);
return successor;
}

注意事项

在每一次对子树进行修改之后需要进行 update,否则会遇到一些奇奇怪怪的 bug(有可能样例并未存在这种 bug,当然对拍是个好东西)。

时间复杂度

巨坑待填

最后有亿些比较简单的练习

  • 洛谷 P3369 【模板】普通平衡树
  • 洛谷 P6136 【模板】普通平衡树(数据加强版)
  • 洛谷 P3391 【模板】文艺平衡树
  • 洛谷 P2234 [HNOI2002] 营业额统计