FHQ-Treap 学习笔记
前言
学了 \(\text{Splay}\)，就顺便把之前洛谷博客上的 \(\text{FHQ-Treap}\) 笔记搬下来复习一下。
简介
FHQ-Treap 是一种平衡树。它的平衡原理和 Treap 一样，但是维护平衡的方式不一样。它并不依赖旋转来维护平衡，而是依赖 分裂 与 合并。
它的代码简短，实现简单，功能强大（理论上可以支持可持久化与序列操作）。
本文将引用一些链接，以保证更好观感，感谢这些博主的博客教会了我这个数据结构。
实现
我们将会讲解它的实现。
首先我们从一些简单的开始。
前置定义
每个 FHQ-Treap 的节点保存了左儿子，右儿子，节点值，随机值，子树大小。
我们再使用 \(n\) 表示题目的操作数，\(tot\) 表示总节点数，\(root\) 表示根，三个 \(tmp\) 表示我们进行操作会用到的三个临时的根。它们的顺序也满足：\(t[tmp1].val
struct FHQ_Treap{
int lc,rc;
int val;
int rnd;
int size;
}t[N];
int n,tot,root;
int tmp1,tmp2,tmp3;
基本操作
-
\(\text{update}\)
\(\text{update}\) 操作用于更新某个节点为根的子树大小。
void update(int x)
{
t[x].size = t[t[x].lc].size + t[t[x].rc].size + 1;
}
-
\(\text{newnode}\)
\(\text{newnode}\) 操作用于开一个新节点。
int newnode(int val)
{
tot++;
t[tot].size = 1;
t[tot].val = val;
t[tot].rnd = rand();
return tot;
}
功能实现
我们先不考虑最难的 \(\text{spilt}\) 和 \(\text{merge}\)。假设我们已经实现了它们的功能，可以直接调用：
-
调用 \(\text{void spilt(int now,int val,int &x,int &y)}\) 可以把以 \(now\) 为根的树按照 \(val\) 分成两棵树：\(x\) 的权值全部小于等于 \(val\)，\(y\) 的则大于。这里 \(x\) 和 \(y\) 是根节点的下标。
-
调用 \(\text{merge(int x,int y)}\) 可以把以 \(x\) 和 \(y\) 为根的树合并，返回新的根节点的编号。
这里我们的 \(x\) 的节点的值必须小于 \(y\) 的节点的值，而且 \(x\) 和 \(y\) 必须是 “经过某次分裂之后” 得到的。（当然，如果是插入操作，一个全新的只有根的节点也可以看作是“经过某次分裂之后”）
好的。那么我们看一下平衡树的基本操作：
这些操作在分裂之后，合并的时候记得维护新的根节点。
-
\(\text{Insert}\)
\(\text{Insert}\) 函数支持我们插入一个值为 \(val\) 的新节点。
我们可以这么考虑：先把原来的树按照 \(val\) 进行分裂，之后得到的是 \(tmp1,tmp2\)。假设我们新增节点的下标是 \(x\)，我们的三个根节点的顺序应该是 \(tmp1,x,tmp2\)。把它们三个合并即可。
void Insert(int val)
{
spilt(root,val,tmp1,tmp2);
root = merge(merge(tmp1,newnode(val)),tmp2);
}
-
\(\text{Delete}\)
\(\text{Delete}\) 函数支持我们删除一个值为 \(val\) 的节点。
我们可以把树按照 \(val\) 分裂，得到 \(tmp3\)。之后按照 \(val-1\) 分裂，得到 \(tmp1,tmp2\)。这样，我们的 \(tmp2\) 就是权值为 \(val\) 的节点。
直接合并 \(tmp2\) 的左右儿子得到新的 \(tmp2\)，这个值为 \(val\) 的节点就消失了。之后按顺序合并 \(tmp1,tmp2,tmp3\) 即可。
void Delete(int val)
{
spilt(root,val,tmp1,tmp3);
spilt(tmp1,val - 1,tmp1,tmp2);
tmp2 = merge(t[tmp2].lc,t[tmp2].rc);
root = merge(merge(tmp1,tmp2),tmp3);
}
-
\(\text{QueryRank}\)
\(\text{QueryRank}\) 操作支持我们查询权值为 \(val\) 的节点的排名。
我们可以把树按照 \(val-1\) 分裂，之后左子树的大小 + 1 就是排名。
void QueryRank(int val)
{
spilt(root,val - 1,tmp1,tmp2);
printf("%d\n",t[tmp1].size + 1);
root = merge(tmp1,tmp2);
}
-
\(\text{Kth}\)
\(\text{Kth}\) 操作支持我们查询给定排名 \(rank\) 的节点的权值。
这个其实就和普通 Treap 没啥不一样。
- 如果 \(rank\) 不大于左子树 \(size\)，走左子树
- 如果 \(rank\) 和左子树大小 + 1 相等就找到了，直接返回
- 不然就把 \(rank\) 减去左子树大小 + 1，之后进右子树寻找
int Kth(int now,int rank)
{
while(1)
{
if(rank <= t[t[now].lc].size)
{now = t[now].lc;continue;}
if(rank == t[t[now].lc].size + 1)
return now;
rank -= t[t[now].lc].size + 1;
now = t[now].rc;
}
}
-
\(\text{QueryPre}\ and\ \text{QueryNxt}\)
\(\text{QueryPre}\) 支持我们查询值为 \(val\) 的节点的前驱，\(\text{QueryNxt}\) 支持我们查询值为 \(val\) 的节点的后继。
查询前驱时，我们按照 \(val-1\) 分裂，左子树 \(tmp1\) 里的值都小于 \(val\)。那么左子树里最大的数，也就是左子树里排名为左子树 \(size\) 的就是前驱。
查询后继时，我们按照 \(val\) 分裂，右子树 \(tmp2\) 里的值都大于 \(val\)。那么右子树里最小的数，也就是右子树里排名为 \(1\) 的就是后继。
void QueryPre(int val)
{
spilt(root,val - 1,tmp1,tmp2);
printf("%d\n",t[Kth(tmp1,t[tmp1].size)].val);
root = merge(tmp1,tmp2);
}
void QueryNxt(int val)
{
spilt(root,val,tmp1,tmp2);
printf("%d\n",t[Kth(tmp2,1)].val);
root = merge(tmp1,tmp2);
}
到这里，我们用分裂与合并解决了平衡树的操作。可以看出，这样做很简洁，很优美。
分裂与合并
我们逃不开的是分裂和合并这两个核心操作。我们之前的操作都是建立在分裂与合并基础上的。
要记住这里的实现是：
分裂出的左树 \(\le val\)，右树 \(> val\)。
-
\(\text{spilt}\)
这里不再赘述它的作用。
分裂的方式分为 “按权值分裂” 和 “按子树大小分裂。这里实现按权值分裂。
我们每次分裂的时候按照这样的规则执行：
-
比较根节点权值与 \(val\) 的大小关系
- 如果小于等于 \(val\)，当前的根和左子树都归入分裂出的左树，递归进右树分裂。
- 否则，根和右子树都归入分裂出的右树，递归进左树分裂。
-
如果进入叶子节点，退出。
单次分裂复杂度 \(O(\log n)\)。
-
void spilt(int now,int val,int &x,int &y)
{
if(!now) {x = y = 0;return;}
if(t[now].val <= val)
x = now,spilt(t[now].rc,val,t[now].rc,y);
else
y = now,spilt(t[now].lc,val,x,t[now].lc);
update(now);
}
-
\(\text{merge}\)
作用也不再赘述。
我们考虑根据它的随机值。我们称 \(x\) 为左树，\(y\) 为右树。
-
比较左树和右树的随机值
- 如果左树随机值小，左树根作为新的根，新树 继承左树的左子树，递归合并 右树 和 左树的右子树，作为新树的右子树。
- 否则，右树根作为新的根，新树 继承右树的右子树，递归合并 左树 和 右树的左子树，作为新树的左子树
-
左树或者右树不存在则退出。
这样就实现了把两棵树合并为一棵。
-
int merge(int x,int y)
{
if(!x || !y) return x + y;
if(t[x].rnd < t[y].rnd)
{
t[x].rc = merge(t[x].rc,y);
update(x);
return x;
}
t[y].lc = merge(x,t[y].lc);
update(y);
return y;
}
这个过程不容易理解。可以配合上述算法流程，观看 ARFA- 的图解FHQ-Treap 的分裂和合并的图解。当然，前面简单的操作也有图解。
小结
综合以上代码就可以实现一个 FHQ-Treap。
一个可以通过【模板】普通平衡树的代码：云剪贴板-FHQ-Treap，模板-普通平衡树
这部分内容主要参考了 ，我结合自己的理解顺序对其进行了重排和修改。
序列操作
FHQ-Treap 可以对于序列进行操作，代替 Splay 的作用。
我们的 \(\text{spilt}\) 变成 按照子树大小分裂。调用 \(\text{spilt(int\ now,int\ k,int\ \&x,int\ \&y)}\) 可以把它分成两棵树，第一棵大小为 \(k\)。
这个就和根据排名查值有点类似。
void spilt(int now,int k,int &x,int &y)
{
if(!now) {x = y = 0;return;}
if(k <= t[t[now].lc].size)// 左子树内部进行分裂
y = now,spilt(t[now].lc,k,x,t[now].lc);
else// 左子树被分裂出去，进入右子树分裂
x = now,spilt(t[now].rc,k - t[t[now].lc].size - 1,t[now].rc,y);
update(now);// 更新当前节点
}
之后就可以愉快地进行序列操作了。
然后你发现：我不理解，我背板子把！但是：
我超！我记不住！
实际上！只需要！记一个！不然你就寄了！因为这个和上一个是很对称的。你发现！其实！这个的分支和上一个相反的！（虽然有一些细节不是很一样）
- 区间操作
具体而言，每次对于区间 \([l,r]\) 操作的时候，我们都先把它 \(\text{spilt}\) 成三部分：\((\cdots,l-1),(l,r),(r+1,\cdots)\)。也就是执行 \(\text{spilt(l-1)}\) 和 \(\text{spilt(r)}\)。
比如 P3391 【模板】文艺平衡树，要求支持区间翻转。那么我们 以序列下标为关键字 把这个序列扔进平衡树。这样，平衡树里面维护的是下标的有序性。
具体而言就是一个一个申请新节点，暴力 \(\text{merge}\) 它和根。其实可以一次性通过一个 \(\text{build}\) 操作进行建树，但是暴力也够用。
加个 \(lazytag\)，表示是否区间翻转。这个是可以在修改操作的时候直接打上标记，在 \(\text{pushdown}\) 的时候再修改，给孩子打标记。
也可以和线段树保持一致，修改操作的时候就直接翻转，打标记，\(\text{pushdown}\) 的时候给孩子修改，打标记。
具体地，对于每个操作，直接分裂出它区间对应的树根打上标记，再合并回去。对于 \(\text{spilt}\) 和 \(\text{merge}\) 而言，都需要先进行一次 \(\text{pushdown}\)，再搞其他操作。而 \(\text{pushdown}\) 就是直接交换这个点的左右子树，更新两个儿子的标记，再把自己的标记清空。
最后的序列可以经过一次从根进行的中序遍历得到。这个是 BST 的基本性质。
代码：云剪贴板-P3391-文艺平衡树-FHQ-Treap
- 序列操作
这个在下面的例题里面。
引用与鸣谢
本文内容参考于以下几个博客，在此再次表示感谢：
cgheavenhealer-FHQ_Treap学习笔记
ARFA-题解 P3369 【【模板】普通平衡树】
远航休息栈-fhq-treap总结
一个小屁孩-题解 P3391 【【模板】文艺平衡树（Splay）】
顺便 \(\%\%\%\) \(\text{Luckybolck}\)！（单方面膜拜大佬）
一些例题
P2234 [HNOI2002]营业额统计
经过胡乱分析，知道这个题要求前驱和后继。
抄抄抄，板子抄完，发现，出问题。
哦！我应该先插一个 \(\inf\) 和一个 \(-\inf\)。
改改改，板子改完，发现，出问题。
输出调试，发现这个板子求的是严格的前驱后继。但是这个题的是不严格的。
就把前驱按照 val - 1 分裂改成按照 val 分裂，后继按照 val 分裂改成按照 val - 1 分裂，让它不严格就可以了。
代码：云剪贴板-P2234
P2286 [HNOI2004]宠物收养场
还是支持求不严格的前驱后继。支持删除。配对时优先考虑和前驱配对。
代码：云剪贴板-P2286
P1486 [NOI2004] 郁闷的出纳员
题意：给一个下限，写一个数据结构，支持：
- 插入一个元素，如果这个元素小于下限，不插入。
- 给所有元素整体加一个值。
- 给所有元素整体减一个值。
- 支持查询第 \(k\) 大 的值。
- 对于任意时刻，元素被加减之后，低于下限那么删除。
要求：对于每个类型 \(4\) 的询问，输出这个值，或者这个值，不存在，为 \(-1\)。最后输出所有要求 \(5\) 统计到的删掉的元素的总数。
题解：
首先看到整体加减，就不难想到拿一个 \(tag\) 维护。那么我们就有：
\[\begin{aligned} val + tag & < minn \\ val & < minn - tag \end{aligned} \]其中 \(minn\) 是下限。
那么我们依据 \(\text{FHQ-Treap}\) 的分裂操作，每次对于 \(tag\) 修改之后，把所有的 \(\le minn - tag - 1\) 的元素裂到左子树，之后直接让根等于右子树，也就删掉了左子树。删除的个数就是左子树的 \(size\)。
因为我们的分裂，分裂出的是一个形如 \([\cdots],(\cdots]\) 的区间，你要是直接裂出 \(< minn - tag\) 的元素到左子树的话是按照 \(minn - tag - 1\) 分裂的。
之后我们插入元素的时候，首先是只插入那些按照题意，满足 \(val \ge minn\) 的。但是你现在的 \(tag\) 是全局有效，但是你在某些 \(tag\) 之后插入的元素其实并不被 \(tag\) 修改。那么怎么办？
我们直接插入 \(val - tag\) 即可。原因：
\[\begin{aligned} val - tag & < minn - tag \\ val & < min \end{aligned} \]你一整理，发现你只要插入的时候按照 \(val - tag\) 插入就能消除当前 \(tag\) 对于 \(val\) 的影响。但是最后输出的时候要记得加上 \(tag\)。
再就是查询第 \(k\) 大 了。我们的平衡树的 \(\text{Kth}\) 显然是查询第 \(k\) 小的。其实你稍微想一下，自己举几个例子就发现，其实第 \(k\) 小的就是第 \(n - k + 1\) 大的。这里的 \(n\) 就是树的元素个数，可以拿 \(t[root].size\) 获取。
这样就完成维护。
代码：云剪贴板-P1486
P3850 [TJOI2007]书架
序列操作。
题意：给定一个序列，支持单点插入，单点查询。
题解：
对于序列操作的题目我们按照 \(size\) 进行 \(\text{spilt}\) 操作。
这个题里面我们把字符串映射为一个整数扔进平衡树里面。之后，对于单点插入，按照位置裂开，把它扔进去。对于单点查询基本不变。一个完全一致的 \(\text{Kth}\)，之后每次询问先按照询问位置裂开为左子树 \(tmp1\)，右子树 \(tmp2\)，之后把右子树裂一个出来，裂为 \(tmp3\) 和 \(tmp4\)。这时候 \(tmp3\) 的值就是对应字符串编号。最后把 \((tmp1,(tmp3,tmp4))\) 合并即可。
代码：云剪贴板-P3850
P2042 [NOI2005] 维护数列
序列操作。
题意：给一个序列，支持以下操作：
- 在
pos位置后插入tot个数。 - 删除从第
pos个位置开始的tot个数。 - 推平从第
pos个位置开始的tot个数。 - 翻转从第
pos个位置开始的tot个数。 - 求从第
pos个位置开始的tot个数的和。 - 求全局的最大子段和。
其中，序列长度保证在任意时间都 \(\le 5 \times 10^5\)，插入的数字保证总数不超过 \(4 \times 10^6\)。
一图流题解：
建议右键图片，在新标签页打开并观看。
这个序列操作全家桶是真的麻烦。要有很清晰的思路才能开始写。
这里说一些细节：
- 翻转标记和推平标记随便先传哪一个都可以。
- 这个题的节点要维护很多信息，直接开开不下，需要把删掉的节点扔进一个内存池（比如一个栈）里来维护删掉之后腾出来空间的节点编号，新建节点重复利用。
- 这个题的暴力插入是不可以的，对于一个区间每一个数都 \(\text{spilt}\) 一次再 \(\text{merge}\) 一次实在是花费太大。只能采用类似线段树的递归建树，再合并进去。
- 这个题翻转之后，左右端点的最大左右子段和也要翻转。
- 这个题最大子段和不能选空的子段，至少要选一个，所以我们的左右子段和可以和 \(0\) 取 \(\max\) 表示选空，但是总子段和在很多处需要更新的时候至少是 \(val\) 来保证非空。
- 新建节点的时候由于你很有可能是从内存池里蒯来一个点，所以你要删掉之前的信息。
- 初始数列拿 \(\text{build}\) 构建好之后应该把
root指向初始树。
代码：云剪贴板-P2042
P4008 [NOI2003] 文本编辑器
序列操作。
题意：写一个数据结构，支持以下操作：
- 把当前指针位置
ptr更改为第pos个字符后面。 - 在当前指针位置
ptr后面插入一个长度为 \(n\) 的字符序列。 - 在当前指针位置
ptr后面删除一个长度为 \(n\) 的字符序列。 - 输出当前指针位置
ptr后面 \(n\) 个字符。 - 当前指针位置
ptr前移一个字符。 - 当前指针位置
ptr后移一个字符。
题解：
区间插入，区间删除，区间查询。这个是可以块状链表做的，但是为什么不拿平衡树写一下呢？
经过了上一题序列操作全家桶的洗礼，我们滴序列操作能力已经大大加强了。于是这个题就写了几下就切了...吗？
所以不再赘述做法。记录一下我的傻逼错误：
写挂了几个地方：
\(\text{spilt}\) 记混了。但是发现了不会记混的方法！
输出应该是 “左 \(\rightarrow\) 根 \(\rightarrow\) 右”。
毒瘤的数据输入格式。逐字符读入写错了。
局部变量和全局变量重名了。
但是！基本无伤大雅。
然后这题挺恶心的就是告诉你最大可能有 \(2M\) 的字符。但是 \(2M\) 有多少个？还好它告诉你 \(1M = 1024 \times 1024\) 字节。也就是 \(1M = 2^{20}\) 字节。但是 char 几个字节来着？我们开个测试程序输出 sizeof('A') 发现，一个字节。那么我们需要给平衡树开 \(2^{21}\) 的空间。
代码：云剪贴板-P4008
P4567 [AHOI2006]文本编辑器
序列操作。
题意：写一个数据结构。其中，支持的操作与 P4008 [NOI2003] 文本编辑器 不同的地方在：支持区间翻转；区间输出变成单点输出。
题解：
加强版。加强的不止是旋转操作，主要是毒瘤读入。然后还有一些奇怪的输出问题。具体可以加、看讨论区。我这不再赘述了。
这个区间翻转就和文艺平衡树一样。
题号是 \(4567\) 的屑题。
代码：云剪贴板-P4567
P3224 [HNOI2012]永无乡
题意：给一张图，支持：
- 联通两个点。
- 查询和一个点联通的点中，第 \(k\) 小的点编号。
题解：
可以很容易想到用并查集维护连通性！
可以很容易想到合并两个平衡树！
怎么合并？好像不是很好整？
启发式合并！把小树暴力拆掉合并进大树里面！
然后就结束了。