关于使用 Fhq Treap 维护序列的小研究

vvauted · 2021-12-10 21:11:22 · 个人记录

前言

众所周知， \text{Fhq Treap} 拥有不俗的维护序列的能力，本文通过一些较为经典（简单）的题目来说明。

宏定义一些变量：

$R_x$： $x$ 的右儿子。 $id_x$： $x$ 在序列中的编号。 $rank_x$：$x$ 在其所在树中的排名。 $T_L$ 与 $T_R$：分裂出的左右树。 $root_x$：树 $x$ 的根。 $siz_x$：以 $x$ 为根的子树的大小。

按排名分裂，单点维护序列

维护的 \text{Fhq Treap} 特点是：

每个节点代表序列中的一位，且节点按 id 排名。

则有推论：

id_x = rank_x

重点：

可以类比普通平衡树的维护方法，这两者之间的区别几乎仅在于分裂的方法不同。

P3850 [TJOI2007]书架

一句话题意：

维护序列，支持：在 pos 位插入一个元素，查询第 pos 位上的元素。

这是一道使用 \text{Fhq Treap} 按排名分裂维护序列的好题。

对于第一种操作，按照普通平衡树插入节点的方法去处理，只不过改成了按排名分裂。
对于第二种操作，直接查询 kth 即可。

P3391 【模板】文艺平衡树

一句话题意：

维护序列，支持：区间反转，查询当前序列

使用一个节点去维护序列上的一位，瓶颈在于怎么一次性拿出一个区间。

按照普通平衡树的套路，假设按 pos 分裂得到两树值域为： [\min,pos-1], [pos,\max]，要想拿出值域 [l,r]，则：

首先 split(l)，得到两树值域为 [min,l-1],[l,\max]

然后在右树上 split(r + 1)，得到：[l,r],[r+1,\max]，此时拿出左树即可。

那么使用维护序列时拿出区间 [l,r] 也同理，只不过是改为按排名分裂罢了。

那么：

初始时可以使用类似线段树的方法建树，有如下代码：

int build(int l, int r) {
    if(l > r) return 0; 
    int o = ++ tot; id[o] = mid;
    L[o] = build(l, mid - 1);
    R[o] = build(mid + 1, r);
    return 0;
}

对于第一种操作，拿出区间 [l,r] 后，在根节点打上 reverse 的标记，在 push\_down 的时候交换左右儿子，再给左右儿子打上 reverse 标记即可。

感性理解：全树交换后所有大小关系都将反转，则全树的 rank 反转，那么由于 rank_x=id_x，那么 id 也跟着反转了。

对于第二种操作，中序遍历全树即可，性质在此：

P4309 [TJOI2013]最长上升子序列

一句话题意：

依次插入从 1 到 n 的数字至指定位置，每次插入求全局最长上升子序列的长度

一道简单的应用题，因为插入的数是单调递增的，所以新插入的数可以跟左侧的任何位置组成上升子序列。

每个节点维护信息 f 与 g，分别代表其子树内最长上升子序列长度的最大值与以当前节点为终点组成的最长上升子序列长度，显然 f 值可以通过 push\_up 来处理，考虑怎么维护 g :

如果在第 pos 个数的右侧插入一个数 i，先 split(pos + 1) 得到 [1,pos],[pos +1,i - 1]，由于刚才推得的性质：

新插入的数可以跟左侧的任何位置组成上升子序列。

那么从左侧选择最长的上升子序列与其组成上升子序列，则这个上升子序列就是以 i 为结尾的最长上升子序列。

易知：左侧选择最长的上升子序列的长度即为左树根的 f 值，则：

g_i=f_{root_{T_L}} + 1

得到 g_i ，与当前最长上升子序列比较后，如果更大则更新，之后再按照普通平衡树的套路合并为整数。

按排名分裂，维护序列连续段

显然一个节点代表一个位置的效率过低，考虑以一个节点维护一个连续段的方式维护序列。

维护的 \text{Fhq Treap} 特点是：

每个节点代表序列中的一段 [l,r]，大小关系为：

r_{L_x}<l_{x}\leq r_{x}< l_{R_x}

重定义 siz_x 为：

siz_x = siz_{L_x} + siz_{R_x}+(r_x-l_x+1)

如果对于每个节点维护其区间长度 len，则：

siz_x = siz_{L_x} + siz_{R_x}+len_x

即为子树维护区间的长度，这样类比按排名分裂，单点维护序列的维护方法，好像有了一些共同点。

按照这样的 siz 统计法，则有推论：

l=rank_x,r =rank_x + len_x-1

重点：

可以类比按排名分裂，单点维护序列的维护方法，并需要一定的自主思考能力。

使用 \text {Fhq Treap} 维护 \text{ODT}

那看看需要实现的最基本操作：**区间覆盖** 既然要区间覆盖，必然需要从 $\text {Fhq Treap}$ 中拿出这个区间。之前在单点维护序列时也遇见过类似的操作，**当时的做法是：使用了两次分裂，第一次刨去左边的，第二次刨去右边的**。假设要拿出线段 $x$： $[l_x,r_x]$ 按照这个套路，先想想怎么刨去左边的：在线段 $x$ 左边（不相交）的线段 $y$ 一定满足：$r_y<l_x$，如图： ![](https://cdn.luogu.com.cn/upload/image_hosting/5jbmrn8x.png) 我们可以按右端点分裂，将右端点小于 $l_x$ 的都分裂出去。然后我们需要刨去右边的：在线段 $x$ 右边（不相交）的线段 $y$ 一定满足 $r_x<l_y

按左端点分裂，将左端点大于 r_x 都分裂出去，则当前树上所有节点都与线段 x 相交。

那么还需要考虑一种情况，就是线段 y 与线段 x 相交但溢出了，如图：

这种线段 y 只可能出现在边缘情况，我们不妨找到树中的这两个边缘节点并特判，如果溢出则像 \text{ODT} 一样分裂后把多余的插入回去。

那么我们得到的这个树就维护了区间 [l_x,r_x] 的信息。

一种节约内存的做法：

对于一些题目，我们可以只维护部分序列信息，如：维护 0,1 序列中的 1。

那么我们可以对于每个区间记录 l,r，然后按照左右端点分裂即可。

如果需要插入时我们可以打上 l,r 平移的 tag

例题：[Ynoi2014] 人人本着正义之名