FHQ-Treap学习笔记

## 参考文章 [洛谷日报第119期 浅析Treap——平衡树 by曦行夜落](https://www.luogu.com.cn/blog/HOJQVFNA/qian-xi-treap-ping-heng-shu) [关于非旋FHQ-Treap的复杂度证明](https://www.cnblogs.com/winlere/p/12098765.html) [洛谷日报第43期 不用旋转的treap？——fhq treap by Chanis](https://www.luogu.com.cn/blog/Chanis/fhq-treap) ## 前置芝士 **定义一个节点的权值为 $val$ 。** **BST(二叉查找树)：** 一棵二叉查找树的本质是一颗二叉树，也就是一个节点至多有两个儿子，性质是左子树的任意 $val < $ 根节点的 $val < $ 右子树的任意 $val$ ，利用此点性质维护一个节点及其子树的大小，我们就可以查找第 $k$ 大 $val$ ，或某一 $val$ 的排名。 [洛谷日报第2期 关于二叉查找树的一些事儿（bst详解，平衡树入门）by ztz11](https://www.luogu.com.cn/blog/ztz11/pinghengshu-bst) **定义一个节点的修正值为 $rnd$ 。** **Heap（堆）：** 默认为二叉堆，分为大顶堆和小顶堆，大顶堆就是根节点的 $rnd > $ 左子树的任意 $rnd$ 且根节点的 $rnd > $ 右子树的任意 $rnd$ ，小顶堆反之。通常用时可以手写或使用STL里的priority_queue，以下默认为小顶堆。 [洛谷日报第11期 浅析基础数据结构-二叉堆 by henry_y](https://www.luogu.com.cn/blog/henry-y/qian-xi-ji-chu-shuo-ju-jie-gou-er-cha-dui) 此处对于 $val$ 或 $rnd$ 相同的点暂且不作讨论，因为对程序无影响，默认权值和修正值都不同（权值是真的没有影响，修正值后面会讲到随机合并）。 **本文不涉及树套树，LCT等基于平衡树扩展的数据结构。** ## 一、Treap（笛卡尔树）的性质 Treap（笛卡尔树）=BST（二叉搜索树）+Heap（堆），这是一棵拥有双重性质的树形数据结构，既满足BST（二叉搜索树）的性质也满足Heap（堆）的性质。 当我们只知道一颗二叉查找树（BST）的 $val$ 的时候，我们可以将任意一个点作为根节点，任意一个比此点 $val$ 小的点作为左儿子，任意一个比此点 $val$ 大的点作为右儿子，按照此种方法建树后，如果我们进行中序遍历，会发现遍历出的序列是有序且一定的。 那么小顶堆（Heap）的性质是修正值最小的点一定在最上方，也就是根，左儿子和右儿子的 $rnd$ 是左子树和右子树分别的最小值，由于有BST的性质限制，又有了Heap的性质限制后我们就发现这棵树的结构也是一定的。 为什么这棵树的结构是确定的？牢牢记住Treap的性质，这棵Treap的根节点**一定是 $rnd$ 值最小的**，且它的左子树的 $val$ 小于它的 $val$ ，它的右子树的 $val$ 大于它的 $val$ ，也就是说，**当我们确定根节点后，它的左右子树的 $val$ 的取值范围就确定了**。接下来发现，它的左子树的根节点**一定是左子树中 $rnd$ 值最小的**，这个点也就是大Treap根节点的左儿子，右儿子同理，**一定是右子树中 $rnd$ 值最小的**，我们会发现，对于每一个节点都是如此，那么一棵树所有的节点的 $val$ 和 $rnd$ 是确定的，结构就是确定的，**结构确定是Treap的本质**。  那么我们发现了，对于一棵Treap中的所有点及其子树都满足上述性质，那么Treap的子树仍然是Treap，一棵Treap中的某一个点及其子树组成的树仍是Treap。 当权值 $val$ 不可控时，可以证明，若关键值 $rnd$ 为随机数，则这棵树的期望深度为 $\log n$ ，就满足了平衡树的要求，具体原因可以参考上文参考文献中关于非旋treap时间复杂度的证明，事实上证明是等价于快速排序的。 下面的图片印证了上文所述。  黑底白字是 $val$ ，白底黑字是 $rnd$ ，进行组合之后成为了结构确定的Treap，不可能出现第二种结构不同的Treap。我们还会发现，这里的 $rnd$ 近似于随机值，隐形地说明了 $rnd$ 值的随机性可以使树高期望为 $\log n$ 。 ## 二、FHQ-Treap的分裂方法 我们已经知道了Treap的结构是确定的，那么如何维护这一棵Treap呢？ Fhq-treap就给出了一种方法，与大多数平衡树用旋转维护不同的是，这种平衡树的维护方法不需要旋转，只需要分裂和合并，FHQ-Treap因此又名非旋Treap。它的优点是代码短，易理解，什么都可以写，缺点是常数略大。 为什么这种维护方法不需要旋转，这是因为Treap的本质——结构确定。 因为从一个根节点开始遍历就可以推出整棵树，所以一个Treap的根节点代表的是这棵Treap所有的点，你可以将其理解为这个Treap所代表的是一个 $val$ 的区间，中序遍历后的 $val$ 序列是单调不减的。 那么比如说一个 $val$ 序列为 $(l,r)$ ，你想要将 $val$ 小于等于 $queryval$ 的所有节点和大于 $queryval$ 的所有节点分开，就相当于将 $val$ 的区间 $(l,r)$ 拆成两个区间 $(l,queryval)$ 和 $(queryval+1,r)$ ，就等同于将一棵大Treap按照 $val$ 分成两棵小Treap，这就是分裂操作。 一旦此棵树的结构确定，我们要分裂区间，**只要保证分出的两个区间树是符合区间边界要求的，且符合Treap的性质，那么这两棵区间树结构就是确定的，那么这种方案的就是正确的，不论是用平衡树常用的旋转或是其它什么方式，只要分出的区间树保证正确，方式就是保证正确的，也就给予了我们创造维护平衡树的新方式！** 那么我们到现在知道了一棵Treap相当于一个区间，分裂等同于拆区间，那么如何拆呢？这就需要利用Treap的性质及本质了。  这张图片应该可以很好的说明Treap如何进行分裂，我们将 $(l,queryval)$ 称为“左区间树”，将 $(queryval+1,r)$ 称为“右区间树”。 当 $queryval=5$ 时，分裂的过程如图，图中的蓝色是已经归入左区间树的点，橙色是已经归入右区间树的点，左右区间树中的实圆是已经确定的节点，虚圆是尚未确定的节点。 我们首先建立两个虚拟节点，就是图中的虚圆，如果当前访问的节点 $now$ 的 $val \leq queryval$ ，那么 $now$ 及 $now$ 的左子树，都应归在左区间树里，就是将左区间树上一个虚拟节点赋为 $now$ ，此节点便由虚变实，然后对 $now$ 建立虚拟的右儿子。否则， $now$ 及 $now$ 的右子树应该归在右区间树里，就是将上一个右区间树的虚拟节点赋为 $now$ ，此节点便由虚变实，然后对 $now$ 建立虚拟的左儿子。如果 $now$ 是空节点，则将左右区间树的虚拟节点赋为 $0$ 。 为什么这样分裂是正确的？当我们对左区间树不断建立虚拟的右儿子时，而 $now$ 的 $val$ 都是单调不减的，所以左区间树满足二叉搜索树的性质，当我们对右区间树不断建立虚拟的左儿子时，而 $now$ 的 $val$ 都是单调不增的，所以右区间树满足二叉搜索树的性质。而这样建树又不会将祖先与后代的关系交换，即便祖父节点变成了父亲节点，它仍是祖先节点，所以左右区间树满足堆的性质。 虚拟节点可以用C++中的int &x来表示左区间树的虚拟节点，int &y来表示右区间树的虚拟节点，这是因为左右区间树任何时候各拥有一个虚拟节点。 因为每访问到一个非空的 $now$ 节点时，递归分裂子树进行的操作会改变左右儿子，所以在维护一些值如子树大小的时候需要用同线段树类似的方法进行上传操作。 **定义一个节点的维护的答案为 $ans$ 。** 一个Treap的根节点的 $ans$ 所维护所代表的是这个Treap所有节点的 $ans$ 。 比如我们在树形结构中经常维护一个值，一个节点及其子树的大小（节点数），那么Treap是二叉搜索树，伪代码就很容易写出来。 **定义一个节点及其子树的大小（节点数）为 $siz$ （包含该节点）。** 伪代码如下： ```cpp void pushup(int now){//上传操作，同线段树类似 tree[now].siz=tree[tree[now].ls].siz+tree[tree[now].rs].siz+1;//now及其子树节点数=其左子树节点数+右子树节点数+1 } ``` 到这里我们可以发现，这一操作就与线段树中的pushup上传操作高度相似，那么在进行递归操作改变左右儿子后我们都要进行pushup上传操作。 那么分裂的函数我们也可以写出来了。 伪代码如下： ```cpp void split(int now,int k,int &x,int &y){//分裂操作，这里的k就是上文中的queryval。 if(!now){x=y=0;return;}//如果当前访问节点为空，将左右区间树的虚拟节点赋值为0。 if(tree[now].val<=k)x=now,split(tree[now].rs,k,tree[now].rs,y);//如果当前节点的val<=k则该节点与其左子树一并归入左区间树，在左区间树中对右儿子建立虚拟节点并继续分裂右子树。 else y=now,split(tree[now].ls,k,x,tree[now].ls);//如果当前节点的val>k则该节点与其右子树一并归入右区间树，在右区间树中对左儿子建立虚拟节点并继续分裂左子树。 pushup(now);//分裂完之后上传左右儿子的维护值至now节点，若now为空在先前就已经return。 } ``` 如果我们要将一个 $val$ 区间的Treap按 $queryval$ 分裂区间，定义 $root$ 为原树的根节点， $x,y$ 为一开始对左右子树建立的虚拟节点，分裂完之后的 $x,y$ 就分别代表了左右区间树的根节点。 伪代码如下： ```cpp int root,x,y;//这个定义应在主函数外定义。 split(root,queryval,x,y);//将原区间(l,r)分裂成(l,queryval)和(queryval+1,r)两个区间树，x就是左区间树的根节点，y就是右区间树的根节点，不论x，y的初始值是什么，因为分裂操作是用的&这一可以赋值的变量，最终的x不是空节点0就是左区间树的根节点，y不是空节点0就是右区间树的根节点。 ``` 如果我们要分裂区间 $(l,r)$ 中的 $(ql,qr)$ ,那么用拆区间的方法，可以将 $(l,r)$ 先拆成 $(l,qr)$ 和 $(qr+1,r)$ ，再将区间 $(l,qr)$ 拆成 $(l,ql-1)$ 和 $(ql,qr)$ 。 伪代码如下： ```cpp int root,x,y,z;//同上，应在主函数外定义 split(root,qr,x,z);//原区间(l,r)分成两个区间(l,qr)和(qr+1,r)，x为左区间树的根节点，y为右区间树的根节点。 split(x,ql-1,x,y);//再将(l,qr)分成(l,ql-1)和(ql,qr)，此时y就是(ql,qr)区间树的根节点，从y进行遍历就是这整个区间的所有节点。 ``` 除了按照权值 $val$ 分裂以外，我们还有**按照**排名，**依靠** $siz$ 分裂（注意，此处排名不等于 $siz$ ），一般应用于序列操作，代替splay之流。 虽然 $siz$ 并不满足二叉搜索树的性质，但排名满足，一个点在中序遍历中的输出顺序就是它的排名，那么一个点的排名就是中序遍历中在它之前输出的点的个数，在二叉搜索树上表现为我们要查找一个排名为 $k$ 的节点，应该从根节点遍历，若 $k=tree[tree[now].ls].siz+1$ ，那么 $now$ 就是目标节点返回，如果 $k \leq tree[tree[now].ls].siz$ ，那么我们要查询的目标节点在 $now$ 的左子树中，进入左子树搜索并 $k$ 值不变。如果都不满足即 $k>tree[tree[now].ls].siz+1$ ，那么我们要查询的目标节点在 $now$ 的右子树中并与此同时应该将 $k=k-tree[tree[now].ls].siz-1$ ，因为目标节点的中序遍历顺序一定比 $now$ 及其左子树的点靠后。 这里给出的二叉搜索树查询排名为 $k$ 的节点的伪代码，对按 $val$ 分裂的Treap适用于查询第 $k$ 大（包括重复 $val$ ）： ```cpp int findkth(int now,int k){//查询排名，前提是该节点存在 while(1){ if(k<=tree[tree[now].ls].siz)now=tree[now].ls;//进入左子树查询 else if(k==tree[tree[now].ls].siz+1)return now;//返回目标节点 else k=k-tree[tree[now].ls].siz-1,now=tree[now].rs;//进入右子树查询 } } ``` 那么这一段二叉搜索树的代码能够帮助我们做什么？它的思想可以很好地帮助我们理解按排名分裂的思想，按照上文权值分裂的步骤，我们发现当 $k \leq tree[tree[now].ls].siz$ 时，我们分裂的目标**边界**（此处的 $k$ 意为将 $now$ 及其子树放入左区间树的节点个数）在左子树中，那么我们将 $now$ 及其右子树放入右区间树并建立虚拟左儿子，否则我们分裂的目标**边界**在右子树中，那么我们将 $now$ 及其左子树放入左区间树并建立虚拟右儿子并进行 $k=k-tree[tree[now].ls].siz-1$ ，当然这一切的前提是 $now$ 不是空节点，否则 $x=y=0$ 虚拟节点赋值为 $0$ 直接返回，一棵按照排名建立的树就分裂成了两棵树，原树的排名为 $(1,n)$ 的会被分裂成 $(1,k)$ 和 $(k+1,n)$ 两棵树，但由于排名分裂依靠的 $siz$ 是不固定的，所以第二棵树的排名变成了 $(1,n-k)$ ，可以将其理解为分为两棵树，第一棵树是原树的中序遍历前 $k$ 个点，第二棵树是原树的中序遍历的剩下的点。 如果找到了目标**边界**后会发生什么，它会一直进入左子树并把目标节点及其左子树所有节点都放进左区间树，所以是满足分裂的。 ## 三、FHQ-Treap的合并方法 如同上文介绍分裂一样，因为Treap的结构是确定的，我们只需要保证操作之后的树符合Treap的性质即可。 我们知道了如何分裂一棵Treap，同时知道，一棵树的树根记录这棵树，这个区间的总的维护信息，如上文所说的 $siz$ ，通过分裂，就可以查询某一段区间的维护值，但我们发现，查询完之后如果我们要再查询另一段区间的维护值，但树已经被我们分裂了，要如何将两棵小Treap恢复成一棵大Treap呢？可以看一下下面对于合并的介绍图片。  如图，我们沿用了上文分裂的例子，黑底白字是 $val$ 权值，而白底黑字是 $rnd$ 修正值。当一个节点被染蓝，说明此节点已被放入最终获得了主树内。 读者或许会注意到，此图内的空节点所连边是实线边而非虚线边，因为这些空节点我们确定会被赋为实值，除非左右区间树皆为空。 我们思考如下的问题：如何进行Treap的合并？ 或许会没有思路，因为我们发现，如果左区间树的 $val$ 范围为 $(3,6)$ 而右区间树的 $val$ 范围为 $(5,7)$ ，那么我们发现它们的 $val$ 值范围是相交的，更可能右区间树的 $val$ 比左区间树小，在遍历时我们就没有很好的办法使其满足Treap的性质，既为二叉搜索树又为二叉堆。 但上文在介绍分裂时，分裂完成的左区间树与右区间树的序列一定是先中序遍历左区间树再中序遍历右区间树得到的序列，区间并不会相交甚至颠倒！这样的话如何满足二叉搜索树的性质呢？要保证合并后的中序遍历序列不变，若两个节点 $u,v$ 分别为左右区间树的根节点，那么 $u$ 及其子树要么在 $v$ 的左子**树**中，要么 $v$ 及其子树在 $u$ 的右子**树**中，这样就可以保证二叉搜索树的性质：中序遍历出原序列。**（注意：是子树而非子节点。）** 如何满足二叉堆的性质呢？刚才我们发现有两种情况，要么 $u$ 为合并后的根且 $v$ 在右子**树**中，要么 $v$ 为根且 $u$ 在左子**树**中，根据二叉堆（小顶堆）的性质， $rnd$ 修正值小者为根，那么解决方案就很明朗了，若 $tree[u].rnd<tree[v].rnd$ 则 $u$ 为根，否则 $v$ 为根。当然，二叉树不可能变成三叉树，将根的方案推到全树，我们需要在第一种情况中将 $tree[u].rs$ 即 $u$ 的右子树与 $v$ 及其子树继续合并，在第二种情况中将 $u$ 及其子树与 $tree[v].ls$ 即 $v$ 的左子树继续合并。若 $u$ 或 $v$ 中任意一个点为空节点时，则非空节点为根，这样我们的伪代码就可以很好地写出了。 **小贴士：左区间树与右区间树不能存在区间相交或顺序颠倒的情况，需满足合并后左区间树节点的中序遍历次序不变，右区间树节点的中序遍历次序为左区间树节点数加原右区间树遍历次序。按权值分裂后合并时需要注意此点，而按照排名分裂后合并时注意左右区间树区间相对位置正确。** ```cpp int merge(int u,int v){ if(!u||!v)return u|v;//如果有任意一个树为空就返回非空的一棵的根 if(tree[u].rnd<tree[v].rnd){//如果u为当前根 tree[u].rs=merge(tree[u].rs,v);//继续合并 pushup(u);//上传 return u;//返回根 } else{//如果v为当前根 tree[v].ls=merge(u,tree[v].ls); pushup(v); return v; } } ``` 至此，FHQ-Treap的最重要操作告一段落，结合分裂和合并我们就可以正确保证一棵Treap的正确性。 ## 四、分裂合并那些事儿 利用分裂合并我们可以做些什么呢？我们可以维护一个有序序列并支持插入、删除、查询指定排名的一个数、查询一个数的排名、前驱、后继等。 ### 插入 插入的本质是将原序列拆成 $(l,queryval)$ 和 $(queryval+1,r)$ 两个区间树，将插入点作为一个点的树，作为右区间树与 $(l,queryval)$ 的左区间树进行合并，或作为左区间树与 $(queryval+1,r)$ 的右区间树进行合并，最后将合并后剩下的两棵区间树按区间顺序进行合并，即将 $(l,queryval)$ 与 $(queryval+1,r)$ 合并或将 $(l,queryval)$ 与 $(queryval,r)$ 合并，这样可以保证没有相交区间，当然，若有左区间树的最大值与右区间树的最小值相等，也是合法的，依然可以正常合并。那么伪代码也很简短。 在此之前，我们要新建一个节点，只需要将信息填入，再随机出一个修正值就可以了。 ```cpp int new_node(int a){//新建节点 tree[++cnt].val=a,tree[cnt].siz=1,tree[cnt].rnd=rand(); return cnt;//此时的cnt代表的是新建节点 } ``` ```cpp void myinsert(int a){插入节点 split(root,a,x,y); root=merge(merge(x,new_node(a)),y); } ``` 如果要按照权值建立有序序列，用权值分裂，如果不是有序序列而是根据点的编号排列，则按照排名分裂插入，如果要插入一段区间只需要建立这段区间的树，将根与原序列的树进行分裂合并即可。 ### 删除 比如我们要删除一个给定权值的点，如果删除所有权值为此的点，只需要分裂出 $(l,queryval-1),(queryval,queryval),(queryval+1,r)$ 三个区间，合并左右两个区间即可。 ```cpp void mydelete(int a){//删除给定权值的所有点 split(root,a,x,z); split(x,a-1,x,y); root=merge(x,z); } ``` 那么删除一个给定权值的一个点，而非所有，该如何做呢？只需要在上文的基础下将分裂出的 $(queryval,queryval)$ 区间树的左右儿子进行合并，这样这棵树的根节点就被删除了，根节点所代表的就是一个点。 ```cpp void mydelete(int a){//删除给定权值的某一点 split(root,a,x,z); split(x,a-1,x,y); y=merge(tree[y].ls,tree[y].rs); root=merge(merge(x,y),z); } ``` ### 查询指定排名的一个数 上文讲述分裂操作时已经提过，不再多叙。 ### 查询一个数的排名 如果是按权值分裂，那么查询给定权值的排名即为查询小于给定权值的数的个数 $+1$ ，分裂即可。 ```cpp int findsiz(int a){//查询一个数值的排名 split(root,a-1,x,y); int k=tree[x].siz+1;//左区间树的大小+1即为排名 root=merge(merge(x,y),z); return k; } ``` 如果我们按照排名分裂，进行了一些**插入删除**的操作后查询某个下标为 $now$ 的节点现在的排名。 无法从根节点开始查询，那么我们应该从这个节点直接一层层暴力回溯，将所有点中序遍历顺序小于等于的点统计即可，由于树深是期望 $\log n$ 的，所以只需要维护每一个节点的父亲，然后就可以了。 如何维护一个点的父亲？在pushup上传时直接维护即可。  如图，白底黑字是Treap的中序遍历顺序，按蓝线划分的Treap节点从左到右看就是中序遍历的序列，我们要查询排名分裂的一个给定点的排名，需要从给定点开始回溯，显然给定点及其左子树大小都是中序遍历小于等于的。每一轮回溯时，若当前点是回溯后的点的左儿子，则回溯点的中序遍历序显然是大于给定点的，不应统计，若是右儿子，则回溯点的中序遍历序显然是小于等于给定点的，可以统计，这样一路回溯到根，根节点没有父亲，就不用统计回溯点信息，直接退出即可，图中橙色即是中序遍历序小于等于给定点的。 ```cpp int findsiz(int now){ int res=tree[now].siz-tree[tree[now].rs].siz; while(now!=root){//由于此种方式维护的父亲不保证根节点的父亲为空 if(now==tree[tree[now].fa].rs)res+=(tree[tree[now].fa].siz-tree[now].siz);//如果当前点为父亲的右儿子，那么根据定义，其父亲及父亲的左子树的排都比当前点小，应被统计入答案，否则其父亲的排名大于当前点则不应统计 now=tree[now].fa;//回溯 }//跳出循环的条件为回溯到根节点即停，为何正确，因为每一个点统计的是自己为其父亲贡献的答案 return res;//返回答案 } ``` ### 查询前驱 定义一个数的前驱为比它小的数中最大的数。 则沿用上文求一个数的排名的方法与查询给定排名的点的方法，先分裂出比这个数小的数的区间，再在此区间中查询最大值，即排名第 $tree[x].siz$ 的数。 ```cpp int findpre(int a){ split(root,a-1,x,y);//分裂为(l,queryval-1)与(queryval,r) int tmp=tree[findkth(x,tree[x].siz)].val; root=merge(x,y); return tmp; } ``` ### 查询后继 定义一个数的后继为比它大的数中最小的数。 则沿用上文求一个数的排名的方法与查询给定排名的点的方法，先分裂出比这个数大的数的区间，再在此区间中查询最小值，即排名第 $1$ 的数。 ```cpp int findpre(int a){ split(root,a,x,y);//分裂为(l,queryval)与(queryval+1,r) int tmp=tree[findkth(y,1)].val; root=merge(x,y); return tmp; } ``` 三两道练习题： [P3369 【模板】普通平衡树](https://www.luogu.com.cn/problem/P3369) [P6136 【模板】普通平衡树（数据加强版）](https://www.luogu.com.cn/problem/P6136) [P2596 【ZJOI2006】书架](https://www.luogu.com.cn/problem/P2596) [P3850 【TJOI2007】书架](https://www.luogu.com.cn/problem/P3850) [P1110 【ZJOI2007】报表统计](https://www.luogu.com.cn/problem/P1110) [P4309 【TJOI2013】最长上升子序列](https://www.luogu.com.cn/problem/P4309) [P5338 【TJOI2019】甲苯先生的滚榜](https://www.luogu.com.cn/problem/P5338) ## 五、上传与下放那些事儿 ### 上传维护值 同线段树类似，一个节点的维护值由其两个儿子的维护值决定，如上文提到的 $siz$ 维护。 如果我们要维护区间和，那么 $tree[now].sum=tree[tree[now].ls].sum+tree[tree[now].rs].sum+tree[now].val;$ 那么什么时候需要上传维护值呢？当一个节点的左右儿子发生的变化的时候，在split和merge的时候就是一个例子。 那么什么时候可以上传维护值呢？当一个节点的左右儿子变化结束之后，尘埃落定的时候，才可以上传，在split和merge的时候就确定了具体的位置，在执行完函数中每一个递归任务后进行pushup。 诸如此类的维护还有许多，同理。这里不再赘述。 ### 下放懒标记 如同线段树一样，对于区间操作，是不能一个个进行修改操作的，我们需要懒标记来记录一个区间操作的暂存信息，只有当我们访问时才下放标记，那么在FHQ-Treap中什么时候下放标记呢？ 答案是当树的结构发生改变的时候，换言之，当我们进行分裂或合并操作时需要改变某一个点的左右儿子信息时之前，应该下放标记，而非之后，因为懒标记是需要下传给儿子节点的，但更改左右儿子信息之后若懒标记还未下放，则懒标记就丢失了下放的对象，就会导致程序的错误。所以在split的时候在赋虚拟节点以信息之前，下放当前 $now$ 节点的懒标记，在merge的时候若 $u$ 为根，则事先下放 $u$ 的懒标记，否则下放 $v$ 的懒标记。 **小贴士：平衡树下放懒标记的时候同样需要考虑不同标记的优先级，比如区间赋值优先级高于其它所有优先级，标记时需要清空其它所有标记。** 同时我们对于下传标记建议这样书写，同线段树类似，打标记时更改维护值，下传时将标记值下传到左右子树并更改左右子树的维护，伪代码如下。 ```cpp void dosth(int now,int tag){ //对于当前点now的维护值改变 //now的懒标记进行修改 //有必要时清空当前点的其它懒标记 } void pushdown(int now){ if(tree[now].tag){ if(tree[now].ls)dosth(tree[now].ls,tree[now].tag);//各种操作 if(tree[now].rs)dosth(tree[now].rs,tree[now].tag);//各种操作 tree[now].tag=0;//懒标记已下传 } } ``` 小贴士：如果平衡树有下放懒标记的操作，同时我们进行排名分裂查找给定点的排名操作时，若下放会改变子树大小，或左右儿子位置，需要先行一层层回溯到根，再从根逐层下传标记，伪代码如下。 ```cpp void myclear(int now){//在findsiz函数中最先调用 if(now!=root)myclear(tree[now].fa);//先回溯父亲节点 pushdown(now);//再下传标记 } ``` 三两道练习题： [P4847 银河英雄传说V2](https://www.luogu.com.cn/problem/P4847) [P1486 【NOI2004】郁闷的出纳员](https://www.luogu.com.cn/problem/P1486) [P4146 序列终结者](https://www.luogu.com.cn/problem/P4146) [P3391 【模板】文艺平衡树](https://www.luogu.com.cn/problem/P3391) [P5217 贫穷](https://www.luogu.com.cn/problem/P5217) 上面这题便是上文提到的按排名分裂查询给定点排名先下放标记。 ## 六、可持久化 **一棵平衡树是可持久化的，当且仅当我们可以将所有在新版本中修改某一节点信息之前对此点建立新点，并保证最终所维护信息的正确，从而不影响历史版本的节点信息。** **新点：指在当前最新版本才建立的点。** **如果在可持久化中你对非新点进行信息的修改，那么就会出错。** ### 分裂合并和下放中的可持久化 可持久化平衡树的概念同可持久化线段树类似，每次只需要将信息改变的点建立新节点，没有改变的点维持原状，将新点连向不需要更改的点，这样中序遍历可以得出新的序列。假如我们每次更改一个点的值，那么这个点就需要建立新点，那么其父亲的儿子信息会发生改变，其父亲需要先行建立新点，以此类推，一直到根，于是我们需要从根遍历，将每一次某些信息改变的点建立新点，这就是可持久化。 那么表现在分裂操作中就为，每次下传 $now$ 的懒标记后，我们需要对某个虚拟节点赋值，那么这个虚拟节点被赋的值不应该是 $now$ ，而是复制了 $now$ 的信息，但下标不为 $now$ 的新点。在合并操作中表现为 $u/v$ 的左右儿子发生改变时，改变的不应该是 $u/v$ 的左右儿子，而是复制了 $u/v$ 信息的新点的左右儿子，这里的左右儿子就像指针一样，只是一个箭头。 **小贴士：有的时候merge中不需要新建节点，当且仅当每一次merge前进行了split操作，也就是合并的Treap作为左区间树时其最右链全为新点，作为右区间树时其最左链全为新点，同时进行任何信息修改的点都必须为新点，包括如下操作但不限于插入、删除。** 伪代码也是较容易写出的： ```cpp int clone(int now){//克隆节点函数 tree[++cnt]=tree[now];//这里默认为结构体数组，直接全复制，仅下标不同 return cnt;//返回下标 } void split(int now,int k,int &x,int &y){//按权值分裂的例子，按排名分裂同理 if(!now){x=y=0;return;} pushdown(now);//操作前先pushdown //如果在这里加上now=clone(now);后面就可以直接下x=now或者y=now，split的函数里也可以直接将now的左右儿子作为虚拟节点，上传也可以上传now的维护值，因为这样做的now已经成为了新点，而now只是早些时候为了split赋的递归值，在这里更改now的值不会影响更早版本的节点信息 if(tree[now].val<=k)x=clone(now),split(tree[now].rs,k,tree[x].rs,y),pushup(x);//如果上面没有now=clone(now)则此处需要建立新点，split中的第一个值可以写tree[now].rs或者tree[x].rs皆可，因为深层递归中此值的改变不影响此层，而第三个值若不写now=clone(now)则只能写tree[x].rs不能写tree[now].rs，因为第三个值作为虚拟节点在深层递归中发生的改变会影响此层，否则tree[now].rs和tree[x].rs皆可，pushup同理 else y=clone(now),split(tree[now].ls,k,x,tree[y].ls),pushup(y);//同理。 } int merge(int u,int v){ if(!u||!v)return u|v; if(tree[u].rnd<tree[v].rnd){ pushdown(u);//先下传再操作 u=clone(u);//由于只会改变一个点的信息，所以只用新建一个点，上文提出过有时不用新建节点 tree[u].rs=merge(tree[u].rs,v); pushup(u);//正常操作 } else{//同理 pushdown(v); v=clone(v); tree[v].ls=merge(u,tree[v].ls); pushup(v); } } ``` 现在我们来解释为什么有时可以在merge省去复制新点的过程，引入最左链，最右链的感念。最左链为树中根节点一直递归左子树直到空所得序列，最右链就是一直递归右子树所得序列，如下图。  蓝色部分就是最左链，橙色部分就是最右链。我们思考split中的左右区间树进行可持久化操作会发生什么，如果这棵树是分裂完的左区间树，那么每一次虚拟节点会赋值一个新点，并将新点的右儿子作为虚拟节点递归，而一旦赋值也一定是新点，这样一来，左区间树的最右链上的点都是新点。同理，如果是右区间树，那么分裂后其最左链上的点都是新点。 再思考merge中的左右区间树会发现，每一次递归中的左区间树都会在更改信息后递归右子树，而右区间树会递归左子树，因为左区间树的最右链都是新点，右区间树的最左链都是新点，新点与新点进行操作，不会影响历史版本。 那么插入为什么不影响呢？因为插入的点若与左区间树合并，则一定在最右链上，若与右区间树合并，则一定在最左链上，插入的点当然是新点，则左区间树的最右链与右区间树的最左链都是新点，仍然满足要求，merge时不用再建新点。 那么删除为什么不影响呢？同理，删除会将一段序列分成三个区间，中间的区间最左链与最右链都是新点，如果仅仅删一个点，中间的区间合并完后最左链与最右链仍都是新点，则本来左区间的最右链和最右链的最左链都是新点，合并的顺序可以随意，只要满足合并完序列正确即可，其他操作同理。 同时我们可以得到一些很好的性质，如果可以合并的左右区间树中，左区间树的最左链都是新点，那么合并完之后的树最左链仍然是新点，如果右区间树的最右链都是新点，那么合并完的树最右链仍然是新点。因为合并后的树的最左链一定由左右区间树的部分最左链组成，最右链一定由左右区间树的部分最右链组成，这样就可以利用这些性质放心地合并，不用考虑过多，就可以正常进行平衡树操作。 那么下传懒标记为什么要新建节点呢？我们考虑到分裂操作只会新建一条最左或最右链的新点，那么其它点是不会被新建的，如果我们进行区间操作，那么下放的左右儿子肯定会有不是新点的，那么下放标记就会影响到这些不是新点的点，从而影响到历史版本的答案，那么我们在下放标记前，就克隆左右儿子的节点，既然下放了，再执行递归，这样递归的点都是新点，也就保证了最左链或最右链全都是新点，这样就不会对历史版本产生影响，保证了可持久化的正确性，伪代码如下。 ```cpp void pushdown(int now){//克隆一般在下放中执行，用以节省空间 if(!tree[now].tag)return;//无标记不用下放 if(tree[now].ls)tree[now].ls=clone(tree[now].ls);//克隆 if(tree[now].rs)tree[now].rs=clone(tree[now].rs);//克隆 if(tree[now].ls)dosth(tree[now].ls,tree[now].tag);//下放标记 if(tree[now].rs)dosth(tree[now].rs,tree[now].tag);//下放标记 tree[now].tag=0;//标记清空 } ``` 三两道练习题： [P3835 【模板】可持久化平衡树](https://www.luogu.com.cn/problem/P3835) [P3919 【模板】可持久化数组（可持久化线段树/平衡树）](https://www.luogu.com.cn/problem/P3919) 当然，只是部分情况可以在merge函数中省去新建节点的操作，那什么情况不可以呢？ 所有上文中可以省的操作都保证了同一点，修改了信息的节点全是新点，我们发现，在下放操作中，只有一个节点存有未下放的懒标记时，才会新建左右儿子的新点，否则不会新建节点。 我们发现标记是会抵消的，那么有没有可能在不新建节点的同时发生错误呢？但在上文的操作中使不会发生，因为所有操作的点都是新点，且保证了每个点左右儿子不变。那么，什么操作会改变某个点的左右儿子呢？很典型的一个例子就是旋转操作，看一下下面这道例题。 [P3835 【模板】可持久化文艺平衡树](https://www.luogu.com.cn/problem/P5055) 我们会发现题解区里的大部分FHQ-Treap都没有在merge中新建节点，虽然可以通过此题，但仍是错误的，因为翻转操作会交换左右儿子，同时翻转操作的标记也是会抵消的，可能父亲和儿子都是新点，儿子原本有标记，但父亲交换后异或清空了儿子的标记，便不会有标记传给后代，到了孙子，其标记为空，便不会新建节点，但孙子节点可能原来不是新点，不在原来的最左链或最右链上，合并后就会存在旧版本的点的信息发生改变，下面给出一个例子。  黑底白字表示节点下标值，白底黑字表示对应的节点修正值 $rnd$ ，此处的下传操作遵循上文的下传操作建议写法。 第一张图为初始时的原树，我们将先翻转前两个点，再翻转前四个点。 要翻转前两个点，首先先拆出前两个点，并翻转后打上标记，得到第二张图。再合并区间得到第三张图，翻转前两个点的操作就执行完了，新建的点即为下标改变的点。 然后翻转前四个点，拆出前四个点并翻转打上标记得到第四张图。之后合并时先推标记得到第五张图，之后合并时便不再有标记要推，合并完得到第六张图。  我们将第一、三、六张图单独拎出来，得到这样一张图，为三个时间依次的历史版本，如果在得到第三个版本后我们再回过头遍历第二个历史版本的树，会发现由于第三个历史版本中的 $8$ 号节点由于没有新建，导致其本来无儿子节点变为有一个右儿子，那么在第二个历史版本遍历时就会出错。 不论是采用哪种下传操作的写法，照此图执行步骤完得到的结果都会出现错误，那么为什么题解里有人通过呢？这是因为如果要出错，不光需要有数据还要程序运行时构造出的 $rnd$ 值符合某些大小关系，否则不会显现出错误，而 $rnd$ 值是随机的，所以有极大概率不会出错，但不在merge中合并是有一定可能会出错的。 如何解决这个问题？每当我们合并的时候新建节点就可以了，不论是不是在分裂时新建过或是在下传中新建过都可以不用去理会了。 还有什么操作必须在merge中新建节点呢？比如将一段区间复制到另一段与之不相交的区间，覆盖掉原来的值，那么在访问到被覆盖的区间时就必须全是新点，每次merge都必须新建节点。 **小结：当一个节点的信息改变会影响到历史版本的值时候，我们需要在分裂中对其新建节点保证可持久化，而一个节点的左右儿子需要下放懒标记时，我们需要对左右儿子建立新点，当操作会影响非新点的点时，我们需要在合并中新建节点。** 三两道练习题（请在阅读完下文的定期重构和随机合并后再做）： [P5350 序列](https://www.luogu.com.cn/problem/P5350) [P5586 【P5350】序列 (加强版)](https://www.luogu.com.cn/problem/P5586) 上面第一道题可以用珂朵莉树做，下面一道题必须要可持久化平衡树+定期重构+随机合并。 **小贴士：对于如上面的题一样的一些不要求查询历史版本信息的可持久化平衡树操作，常常会利用定期重构的方法节省空间。（具体见下文）** ## 七、FHQ-Treap的小伙伴们 ### 垃圾回收 垃圾回收，顾名思义，将删除掉的无用的节点在下次新建节点的时候优先使用。具体实现方法为在删除节点的时候将删除的节点一个个放入队列里，在新建节点的时候判断队列是否为空，如果不为空就从队头取一个节点清空原有的所有信息并新建，否则就按正常情况新建节点。此种操作可以节省空间。 三两道练习题： [P2042 【NOI2005】维护序列](https://www.luogu.com.cn/problem/P2042) ### 笛卡尔树（Treap）的建立 当我们建立一棵笛卡尔树（Treap）时，的确可以按照顺序每新建一个点就将其与前面序列构建的点合并成新的树，最后合并出的就是整个序列的唯一的笛卡尔树。 一般这样子构建出的笛卡尔树是按照排名分裂的，当然不排除对于某些按权值分裂的平衡树初始化时先sort一遍再构造树。 但是这样子的 $O(n \log n)$ 建立方法是不够优秀的，笛卡尔树有根据其性质而来的对已知序列的 $O(n)$ 建树。 我们考虑按照序列从左到右的顺序，也是中序遍历的顺序加入点，那么加入之后这个点一定会在最右链上，那么我们考虑用栈存储这个最右链，那么我们需要一直弹栈，直到栈空或者找到新加点的修正值大于栈顶的修正值，即满足小根堆的性质。 原树的中序遍历序一定比新加点小，然后新加点肯定在最右链上，我们考虑如果栈不为空就将栈顶的右儿子变为新加点，否则不操作。然后最晚被弹栈的点一定就为新加点的左儿子，如果没有弹栈点，那么新加点的左儿子就为空。然后我们要维护最右链，即将新加点压入栈。 我们思考当一个点被弹栈时它的左右儿子，它的子树就固定了，那么在FHQ-Treap的维护中就表示为需要上传维护值。那么构造笛卡尔树完成之后，剩下一条未弹栈的最右链的维护值没有上传，那么我们需要一直弹栈，一直上传维护值，直到栈空。最后我们考虑在执行最后弹栈上传最右链值之前，栈一定不为空，因为这棵树不为空所以最右链不为空，那么这条最右链的栈底就是构建完成的笛卡尔树的根节点，伪代码也较为好写。 ```cpp int build(){//笛卡尔树O(n)建立 int top=0,x=0,last=0;//top栈顶指针，x新点下标，last最晚被弹栈的点 for(int i=1;i<=n;++i){ x=new_node(a[i]),last=0;//初始 while(top&&tree[s[top]].rnd>tree[x].rnd){pushup(last=s[top]),s[top--]=0;}//不断弹栈 if(top)tree[s[top]].rs=x;//栈不为空栈顶的右儿子为新加点 tree[x].ls=last,s[++top]=x;//新加点左儿子为最晚被弹栈点，并1压栈入当前最右链 } while(top)pushup(s[top--]);//上传最右链 return s[1];//返回根节点 } ``` 再给出一个建树的小例子。  通过 $O(n)$ 的建树，我们可以缩短初始化和插入一段区间的时间。 笛卡尔树还有一些小性质：我们在求静态区间最值（区间最大值/最小值RMQ问题）的时候，不仅可以用上传操作和分裂维护，即按排名分裂，还可以直接将第 $i$ 个点的 $val$ 值作为 $rnd$ 值， $val$ 失去了意义，就不用记录，只需要记录 $rnd$ 即可，如果是求区间最大值建大根堆，，最小值建小根堆，笛卡尔树建完后，一段区间 $(l,r)$ 的RMQ就是中序遍历序为 $l$ 和 $r$ 两个点的LCA的 $rnd$ 值。 其原理为笛卡尔树中根节点的 $rnd$ 值为整棵树区间的RMQ，左子树的中序遍历序比根节点小，而根节点的中序遍历序又比右子树小，那么如果从根节点开始遍历，如果 $l$ 或 $r$ 有一点是根节点，那么RMQ就是根节点的 $rnd$ ，所以根节点既为LCA，又为答案，如果两端点各在左右子树中，那么查询区间一定包含根节点，因为根节点 $rnd$ 为根节点及其子树的RMQ，所以根节点既为LCA，又为答案。如果两端点在同一子树内，即同在左子树或同在右子树，那么查询区间一定包含根节点，那么根节点既不为LCA，又不为答案，答案仍在两端点同在的子树中。依次递归下去，答案一定为两端点的LCA。 三两道练习题： [P5854 【模板】笛卡尔树](https://www.luogu.com.cn/problem/P5854) [P3865 【模板】ST表](https://www.luogu.com.cn/problem/P3865)（配合离线做法用tarjan线性求LCA可以做到理论最优时间复杂度） ### 定期重构 当有些题目中对空间有一定限制，且不要求查询历史版本，我们可以与定期重构，当所用空间超过一个给定值的时候，我们就中序遍历整棵树，存入一个数组里，再线性建树，伪代码如下。 ```cpp void dfs(int now){ pushdown(now);//先下传 if(tree[now].ls)dfs(tree[now].ls); a[++tot]=tree[now].val;//中序遍历 if(tree[now].rs)dfs(tree[now].rs); } int main(){ for(int i=1;i<=m;++i){ if(cnt>mylimit){ tot=0;//清空数组计数 dfs(root); cnt=0;//重构前所建的所有点都失效 root=build();//重构 } } return 0; } ``` 有时题目会有一些特殊的性质限制，对于一些操作后的重构就变得必要。 三两道练习题： [P3987 我永远喜欢珂朵莉~](https://www.luogu.com.cn/problem/P3987) [P5610 【Ynoi2013】大学](https://www.luogu.com.cn/problem/P5610) ### 随机合并 随机合并，顾名思义，就是随机地进行合并，与普通给定 $rnd$ 值不同的是，事先没有在建点时随机关键值，而是在合并时根据随机结果决定合并顺序。这样做的好处是普通合并在某些操作时会导致复制节点出现重复关键值，导致FHQ-Treap的理论时间复杂度退化，而随机合并则能保证时间复杂度正确。这样做的坏处是常数因子会较大，在一般情况下不建议使用，伪代码如下。 ```cpp void merge(int u,int v){ if(!u||!v)return u|v; if(rand()%(tree[u].siz+tree[v].siz)<tree[u].siz){//随机合并 pushdown(u); //u=clone(u);可持久化时用 tree[u].rs=merge(tree[u].rs,v); pushup(u); return u; } else{ pushdown(v); //v=clone(v); tree[v].ls=merge(u,tree[v].ls); pushup(v); return v; } } ``` 因为合并只会改变左区间树的最右链和右区间树的最左链，一句话概括随机合并的使用方法：除了合并时的if条件判断，其它一切与正常合并的FHQ-Treap没有不同。 随机合并没有 $rnd$ 修正值，那么在建树的时候我们就可以取最优情况，即一棵二叉树，每次将当前区间的最中间点作为根节点，再递归左子树，右子树，伪代码如下。 ```cpp int build(int l,int r){ if(l>r)return 0;//左端点大于右端点即非法 int mid=(l+r)>>1;//取最优情况 int now=new_node(a[mid]);//a数组就是中序遍历出的序列 tree[now].ls=build(l,mid-1);//递归左子树 tree[now].rs=build(mid+1,r);//递归右子树 pushup(now);//上传维护值 return now;//返回根节点 } ``` ### 启发式合并 启发式合并其实很简单，我们开始思考对于两个有交集的Treap如何合并，很暴力的方式就是选择其中的一棵Treap，后序遍历整棵树，将每个点左右儿子清空，拆完后作为单点与另一棵树暴力插入。然而这样的时间复杂度是不优秀的，我们考虑每次将较小的树合并到较大的树上，这样每个点最多只会合并 $\log n$ 次，一共 $n$ 个点，每次合并 $O(\log n)$ 的时间复杂度，一共就是 $O(n \log^2 n)$ 的时间复杂度，伪代码很好写。 ```cpp void dfs(int x,int &y){//暴力合并 if(!x)return; dfs(tree[x].ls,y); dfs(tree[x].rs,y); tree[x].ls=tree[x].rs=0;//清空左右儿子 split(y,tree[x].val,a,b); y=merge(merge(a,x),b); } int mymerge(int x,int y){ if(tree[x].siz>tree[y].siz)swap(x,y);//启发 dfs(x,y); return y; } ``` 三两道练习题： [P3224 【HNOI2012】永无乡](https://www.luogu.com.cn/problem/P3224) [P3201 【HNOI2009】梦幻布丁](https://www.luogu.com.cn/problem/P3201) ### 区间缩点 有的时候空间限制或题目特殊限制，我们不可以对于每一个元素都开一个点，只能将一段连续的区间缩成一个点。 #### Part 1 双平衡树（动态开点平衡树） 对于一段连续区间开点，操作到区间中某一点再将区间分成几段进行操作。 例题：[P3285 【SCOI2014】方伯伯的OJ](https://www.luogu.com.cn/problem/P3285) 对于按照排名分裂的平衡树要求查询给定编号的点，我们需要建立不止一棵平衡树，排名分裂用FHQ-Treap，编号用STL里的map红黑树，对于未被操作的一段连续区间缩成一个点并记录左右端点，对于这段区间的右端点在map中记录对应的FHQ-Treap节点下标，查询某个编号所在FHQ-Treap中的下标，只需要调用map中的lower_bound即可。若要取出区间中的某一个点，需要先取出这个点所在FHQ-Treap中的区间缩成的节点，分裂区间新建节点即可，给出一段代码。 ```cpp map<int,int>f; inline int new_node(int l,int r){ tree[++cnt].l=l,tree[cnt].r=r,tree[cnt].siz=r-l+1,tree[cnt].rnd=rand(); f[r]=cnt;//红黑树 return cnt; } inline int findsiz(int now){//查询给定下标的点在FHQ-Treap中的排名 int tot=tree[now].siz-tree[tree[now].rs].siz; while(now!=root){ if(tree[tree[now].fa].rs==now)tot=tot+tree[tree[now].fa].siz-tree[now].siz; now=tree[now].fa; } return tot; } inline void changepoint(int a,int b){//假设我们要将编号为a的点改为编号为b的点 int k=f.lower_bound(a)->second;//查询在红黑树记录的编号对应FHQ-Treap节点下标 int l=tree[k].l,r=tree[k].r;//所在区间的左右端点 int rkr=findsiz(k),rkl=rkr-(r-l+1);//查询当前区间右端点在FHQ-Treap中的排名并算出左端点的排名-1 write(lastans=rkl+a-l+1);putchar('\n'); split(root,rkr,x,z); split(x,rkl,x,y);//分裂出当前区间 if(l==r)root=merge(merge(x,new_node(b,b)),z); else if(l==a)root=merge(merge(x,merge(new_node(b,b),new_node(a+1,r))),z); else if(r==a)root=merge(merge(x,merge(new_node(l,a-1),new_node(b,b))),z); else root=merge(merge(x,merge(merge(new_node(l,a-1),new_node(b,b)),new_node(a+1,r))),z);//分类讨论 } int main(){ root=new_node(1,n);//初始化 return 0; } ```  如图，相同颜色的段就代表排名连续并且编号连续并且被缩成的一个FHQ-Treap中的点，箭头就代表其在map中右端点处存储的FHQ-Treap节点下标，相同颜色的编号在map中取lower_bound就可以得到右边最近的箭头所存储的下标。当我们要对一个点进行操作时，将一个点拆成几个点，并在map中右端点处存储对应下标（箭头）。 #### Part 2 模拟珂朵莉树 我们将按排名分裂的平衡树中连续的相同大小元素节点缩成一个点，在需要更改部分段信息时再拆点，可以模拟珂朵莉树。但需要注意的是，题目中的操作下如果这种方法可以打标记，可持久化，那么说明普通平衡树也可以打标记，也可持久化，那么就不如普通平衡树，如果这种方法不可以打标记，那么说明普通平衡树也不可以打标记，那么还不如写珂朵莉树。总之此种方法似乎没有很大的优势，常数又大，所以这里仅仅提出，不建议使用。伪代码如下。 ```cpp void cut(int &now,int lth){ if(lth<=0=||lth>=tree[now].len)return; int t=++cnt; //now=clone(now);可持久化用 tree[t].rnd=rand(),tree[t].ls=tree[now].ls,tree[t].rs=0,tree[now].ls=0,tree[t].len=lth,tree[now].len-=lth;//还需要更改维护信息，此处省略，根据题意来添加 pushup(now),pushup(t); now=merge(t,now);//这个操作的时间复杂度实际上是O(1)的，因为左区间树没有右儿子，右区间树没有左儿子，最多递归到第2层就返回了 } void split(int now,int k,int &x,int &y){ if(!now){x=y=0;return;} pushdonw(now); cut(now,k-tree[tree[now].ls].siz); //now=clone(now);可持久化时用 if(k<=tree[tree[now].ls].siz)y=now,split(tree[now].ls,k,x,tree[now].ls); else x=now,split(tree[now].rs,k-tree[tree[now].ls].siz-tree[now].len,tree[now].rs,y); pushup(now); } ``` #### Part 3 双分裂 对于Part 2，我们深感其用处不多，那么，在不能打标记的情况下，是只能暴力操作，那么我们对于可以打标记的按排名分裂的情况下，还会有一些特殊情况。 例题：[P5066 【Ynoi2014】人人本着正义之名](https://www.luogu.com.cn/problem/P5066) 我们可以延续Part 2的思路，将连续相同的一个极长段缩成一个点，但我们在此题中不用再拆点，保证极长段被缩在一个点里。执行操作，我们需要先取出操作区间，但要保证极长段，又不能拆点，我们就可以通过书写两种操作的方法，将只有部分元素存于操作区间中的节点一并取出。  我们不进行拆点，写两种排名分裂，第一种分裂将左端点排名 $\leq queryval$ 的点分裂进左区间树，其它进右区间树。第二种分裂将右端点排名 $\leq queryval$ 的点分裂进左区间树，其它进右区间树。伪代码如下。 ```cpp void split_l(int now,int k,int &x,int &y){//第一种分裂 if(!now){x=y=0;return;} pushdown(now); if(k<=tree[tree[now].ls].siz)y=now,split_l(tree[now].ls,k,x,tree[now].ls); else x=now,split_l(tree[now].rs,k-tree[tree[now].ls].siz-tree[now].len,tree[now].rs,y);//除非当前节点全部在右区间内，将其归入右区间树，否则就归入左区间树 pushup(now); } void split_r(int now,int k,int &x,int &y){//第二种分裂 if(!now){x=y=0;return;} pushdown(now); if(k<tree[tree[now].ls].siz+tree[now].len)y=now,split_r(tree[now].ls,k,x,tree[now].ls); else x=now,split_r(tree[now].rs,k-tree[tree[now].ls].siz-tree[now].len,tree[now].rs,y);//一旦当前节点有部分在右区间内，就将其归入右区间树，否则归入左区间树 pushup(now); } ``` 那么我们要分裂出一个区间的时候，先第一种分裂对 $r$ 分裂，再用第二种分裂对 $l$ 分裂。 对于三个Part的总的例题： [CF817F MEX Queries](https://www.luogu.com.cn/problem/CF817F) [P3968 【TJOI2014】电源插排](https://www.luogu.com.cn/problem/P3968) 相信FHQ-Treap还有更多可实现的操作等待着我们发现，完结撒花！