概述

顾名思义，$\text{FHQ-Treap}$ 也是一种平衡树，其中序遍历有序。他和 $\text{Treap}$ 一样，都是随机附加域满足堆的性质的二叉搜索树，其期望深度为 $\mathcal O(\log n)$，也正是以此达到相对平衡。

实现

核心操作

分割

通过权值分割

第一棵树中的权值都不大于 $v$，第二棵树中的权值都大于 $v$。

void splitVal(Node *p, int v, Node *&x, Node *&y) {
    if (p == null) {
        x = y = null;
        return;
    }
    if (p->val <= v) {
        x = p;
        splitVal(p->ch[1], v, p->ch[1], y);
    } else {
        y = p;
        splitVal(p->ch[0], v, x, p->ch[0]);
    }
    p->pushup();
}

通过大小分割

第一棵树的大小为 $k$，第二棵树为平衡树剩下的部分。

void splitSize(Node *p, int k, Node *&x, Node *&y) {
    if (p == null) {
        x = y = null;
        return;
    }
    if (k >= p->ch[0]->sz + 1) {
        x = p;
        splitSize(p->ch[1], k - p->ch[0]->sz - 1, p->ch[1], y);
    } else {
        y = p;
        splitSize(p->ch[0], k, x, p->ch[0]);
    }
    p->pushup();
}

合并

有了分割，那么肯定有合并操作。我们需要将两个根指向的树合并起来。假设第一棵树的权值都小于第二棵树。由于 $\text{FHQ-Treap}$ 的平衡条件是随机附加域，因此我们只需要比较两个根的随机值就可以确定整棵树。

假设两个根为 $l,r$，如果 $\text{rand_val}(l)<\text{rand_val}(r)$，那么保留 $l$ 的左子树，将 $l$ 的右儿子和 $r$ 合并得到的新树作为右子树。反之同理。

Node *merge(Node *l, Node *r) {
    if (l == null) return r;
    if (r == null) return l;
    if (l->rnd < r->rnd) {
        l->ch[1] = merge(l->ch[1], r);
        l->pushup();
        return l;
    } else {
        r->ch[0] = merge(l, r->ch[0]);
        r->pushup();
        return r;
    }
}

其他操作

由于 $\text{FHQ-Treap}$ 运用了函数式编程的方法，因此其他的各种操作都是基于 $\text{split}$ 和 $\text{merge}​$ 操作实现的。

插入操作

假如我们要加入的数为 $v$，那么直接把小于等于 $v$ 的数提出来（即为 splitVal(v)），然后把左半边树 $x$ 和 $v$ 节点和右半边树 $y$ 三部分 merge 起来。

void insert(int v) {
    Node *x, *y;
    splitVal(rt, v, x, y);
    rt = merge(merge(x, new Node(v)), y);
}

删除操作

和操作同理，但是略微复杂。考虑一棵树上可能有重复权值的节点，我们需要得到小于、等于、大于 $v$ 三棵树，然后删除等于 $v​$ 的那棵树的根节点（代码实现中可是通过合并两个儿子实现删根），最后重新合并起来。

void erase(int v) {
    Node *x, *y, *z;
    split(rt, v, x, z);
    split(x, v - 1, x, y);
    rt = merge(merge(x, merge(y->ch[0], y->ch[1])), z);
    delete y;
}

查询排名

将 $1$ 到 $v-1$ 的元素提出来得到树 $x$，那么 $v$ 的排名就是 $x$ 的大小加 $1$。

int rank(int v) {
    Node *x, *y;
    split(rt, v - 1, x, y);
    int ans = x->sz + 1;
    rt = merge(x, y);
    return ans;
}

第 k 大数

我们把前 $k-1$ 个数拿出来，再从剩下的树中找第 $1$ 个元素就是答案。使用 splitSize 即可实现。

Node *kth(Node *Rt, int k) {
    Node *x, *y, *z;
    splitSize(Rt, k - 1, x, y);
    splitSize(y, 1, y, z);
    Node *ans = y;
    rt = merge(merge(x, y), z);
    return ans;
}

查询前驱

先得到 $1$ 到 $v-1$ 构成的树，用 kth 函数求出其中最后一个元素即可。

Node *pre(int v) {
    Node *x, *y;
    split(rt, v - 1, x, y);
    Node *ans = kth(x, x->sz);
    rt = merge(x, y);
    return ans;
}

查询后继

先得到 $1$ 到 $v$ 构成的树，用 kth 函数求出剩下的树中最后一个即可。

Node *suc(int v) {
    Node *x, *y;
    split(rt, v, x, y);
    Node *ans = kth(y, 1);
    rt = merge(x, y);
    return ans;
}

区间操作

我们可以轻松提取出这个区间构成的树，然后对这棵树的根节点打标记就行了。

代码

#include <cstdio>
#include <cstdlib>
#include <ctime>

struct Node;
Node *null;

struct Node {
    Node *ch[2];
    int rnd, val, sz;
    Node(int _val = 0) {
        ch[0] = ch[1] = null, rnd = rand(), val = _val, sz = 1;
    }
    void pushup() {
        sz = ch[0]->sz + ch[1]->sz + 1;
    }
};

struct fhqTreap {
    Node *rt;
    fhqTreap() {
        null = new Node();
        null->ch[0] = null->ch[1] = null, null->sz = 0;
        rt = null;
    }
    void split(Node *p, int v, Node *&x, Node *&y) {
        if (p == null) {
            x = y = null;
            return;
        }
        if (p->val <= v) {
            x = p;
            split(p->ch[1], v, p->ch[1], y);
        } else {
            y = p;
            split(p->ch[0], v, x, p->ch[0]);
        }
        p->pushup();
    }
    void splitSize(Node *p, int k, Node *&x, Node *&y) {
        if (p == null) {
            x = y = null;
            return;
        }
        if (k >= p->ch[0]->sz + 1) {
            x = p;
            splitSize(p->ch[1], k - p->ch[0]->sz - 1, p->ch[1], y);
        } else {
            y = p;
            splitSize(p->ch[0], k, x, p->ch[0]);
        }
        p->pushup();
    }
    Node *merge(Node *l, Node *r) {
        if (l == null) return r;
        if (r == null) return l;
        if (l->rnd < r->rnd) {
            l->ch[1] = merge(l->ch[1], r);
            l->pushup();
            return l;
        } else {
            r->ch[0] = merge(l, r->ch[0]);
            r->pushup();
            return r;
        }
    }
    void insert(int v) {
        Node *x, *y;
        split(rt, v, x, y);
        rt = merge(merge(x, new Node(v)), y);
    }
    void erase(int v) {
        Node *x, *y, *z;
        split(rt, v, x, z);
        split(x, v - 1, x, y);
        rt = merge(merge(x, merge(y->ch[0], y->ch[1])), z);
        delete y;
    }
    int rank(int v) {
        Node *x, *y;
        split(rt, v - 1, x, y);
        int ans = x->sz + 1;
        rt = merge(x, y);
        return ans;
    }
    Node *kth(Node *Rt, int k) {
        Node *x, *y, *z;
        splitSize(Rt, k - 1, x, y);
        splitSize(y, 1, y, z);
        Node *ans = y;
        rt = merge(merge(x, y), z);
        return ans;
    }
    Node *pre(int v) {
        Node *x, *y;
        split(rt, v - 1, x, y);
        Node *ans = kth(x, x->sz);
        rt = merge(x, y);
        return ans;
    }
    Node *suc(int v) {
        Node *x, *y;
        split(rt, v, x, y);
        Node *ans = kth(y, 1);
        rt = merge(x, y);
        return ans;
    }
} fhq;

int main() {
    srand(time(0) + *(new char));
    int m;
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if (opt == 1) fhq.insert(x);
        if (opt == 2) fhq.erase(x);
        if (opt == 3) printf("%d\n", fhq.rank(x));
        if (opt == 4) printf("%d\n", fhq.kth(fhq.rt, x)->val);
        if (opt == 5) printf("%d\n", fhq.pre(x)->val);
        if (opt == 6) printf("%d\n", fhq.suc(x)->val);
    }
    return 0;
}

习题

详见「算法笔记」Splay - 维护二叉查找树。