FHQ Treap

\(\text{FHQ Treap}\)是一种好写好用的平衡树。

它的平衡策略和普通\(\text{Treap}\)相似，采用在维护\(\text{BST}\)性质的同时维护随机的堆的形态来维持平衡；
但是维护结构的方式和\(\text{Treap}\)不同，不采用旋转，而是采用拆和合并的方法来维持树和堆的特性。

同时，由于\(\text{FHQ Treap}\)的操作所涉及的节点和基于旋转的其他平衡树相比少（仅\(\log n\)个），它支持可持久化。

---

在实现\(\text{FHQ Treap}\)的时候，一般将多个相同的数作为多个节点保存，这样便于各种针对单个节点的操作。左子树即存放了所有权值\(\leq\)当前节点的点。

Merge

将两棵树合并成一颗树，使得新树含有原来两棵树的所有节点。要求两棵树中的一颗树的所有权值均小于另一棵树的权值。

这是一个递归的过程：我们现在手上有两个子树\(x\)和\(y\)，不妨设权值\(x.val<y.val\)；
我们想让新的树满足小根堆的性质，进而我们要让堆权值\(key\)较小的那个节点在上方；

所以，我们直接把另一个节点和子节点合并成为新的子节点。结合递归的思想，我们就可以得到如下的代码：

node* merge(node* x, node* y) {
    if (!x || !y)                     // 如果两个节点之中有一个空节点：直接返回另一个节点
        return x ? x : y;             // （如果都是空节点就随便返回一个空节点）
    if (x->val > y->val)
        swap(x, y);
    if (x->key < y->key) {
        x->rson = merge(x->rson, y);
        update(x);
        return x;
    } else {
        y->lson = merge(y->lson, x);
        update(y);
        return y;
    }
}

Split

将一颗树以一个权值\(val\)为界拆成两颗树，使得拆出的两棵树中其中一颗\(l\)的所有节点权值\(\leq val\)，另一颗\(r\)的权值\(>val\)。

我们在递归时传入拆出的两棵树当前的子树应该接在的位置（使用引用）。

void splitval(node* p, int val, node*& left, node*& right);

在函数中：

• 如果当前节点为空则\(l\)和\(r\)都设为空。
• 如果当前节点的权值\(p.val \leq val\)，这个节点应当接到\(l\)上：
  我们直接把当前节点接到\(l\)上，然后递归把当前节点的右子，拆到\(l=\) 当前节点右子，\(r=r\)的两个地方。

if (p->val <= val) {
    left = p;
    splitval(p->rson, val, p->rson, right);
}

• 如果当前节点的权值\(p.val \leq val\)，这个节点应当接到\(r\)上：
  和上面一样，我们直接把当前节点接到\(r\)上，然后递归把当前节点的右子，拆到\(l=l\) ，\(r=\) 当前节点左子的两个地方。

else { /* p->val > val */
    right = p;
    splitval(p->lson, val, left, p->lson);
}

完整的代码如下：

void splitval(node* p, int val, node*& left, node*& right) {
    if (!p)
        left = right = 0;
    else {
        if (p->val < val) {
            left = p;
            splitval(p->rson, val, p->rson, right);
        } else { /* p->val > val */
            right = p;
            splitval(p->lson, val, left, p->lson);
        }
        update(p);
    }
}

剩下的写完了再补