FHQ Treap区间操作

分裂操作

FHQ Treap（Fully-Functional Quick-time Heap）是一种类似于平衡树的数据结构，它的定义相对简单，对于每个节点，其拥有一个权值和一个键值。在FHQ Treap中，节点按照权值进行堆排序，根据键值建立BST，在维护堆排序的同时，能够保证BST的平衡。 为了支持区间操作，FHQ Treap在进行区间操作时需要先对其进行分裂操作。其实现过程如下： 1. 对于区间操作[l, r]，先查找到r的后继节点，用splitedSplit将该节点和其前继节点切割成一个小Treap，并将这个Treap中的节点标记。 2. 再查找到l的前驱节点，用splitedSplit将该节点和其后继节点切割成另一个Treap，并将这个Treap中的节点标记。 3. 合并两个被标记的Treap，并记录其最小节点的权值和最大节点的权值，得到新的Treap作为区间[l, r]对应的子树。

区间合并

在FHQ Treap中，区间合并操作十分方便，直接将两个子树链接在一起即可。但这里需要注意的是，合并后的树并不一定是平衡的，需要使用自动平衡的方式来维护Treap的性质。在我实现的代码中，使用了旋转操作和pushup操作来自动平衡。

区间查询

在进行区间查询时，我们需要根据区间的左右端点将Treap切分成三部分：区间内的子树、区间左侧的子树和区间右侧的子树。然后将区间内的子树按照权值排序，计算出结果并返回即可。这里需要注意的是，如果区间内的子树为空，则返回默认值。 就是对FHQ Treap区间操作的详细介绍，相信通过本文的介绍，大家对FHQ Treap的区间操作有了更深入的了解。