深刻浅谈 FHQ-Treap —— 常数可以不大，用法一点不少

SkyWave · 2024-12-08 11:30:23 · 算法·理论

博客仍在更新中，有任何宝贵建议欢迎私信！

前言

OI 中常用的平衡树有很多，但是论码量，一般大家也只会选 splay 或者 treap，但是这两个平衡树经常被说常数很大。\ splay 的常数主要在维护它的结构上，信息合并上的常数还不错，也没啥好说的，这里就不提了。\ 这里说说 treap。\ 很多人说非旋 treap 常数很大，这是因为大家经常用一次 split 两次 merge 来搞一个插入，两次 split 一次 merge 搞一个删除，这就连树的路径都遍历了三遍，而且把平衡树的边各种修改，常数自然就上去了。\ ——Treap, skip2004

我是半年前入门平衡树的。和很多人一样，学的第一种平衡树就是 FHQ-Treap。

众所周知，学完一种数据结构的实现会手痒。做完几道例题后我就自己封装了一个 FHQ-Treap。确认完每个功能都没问题后，我就在想如何优化自己的实现。

其他地方感觉无可挑剔，我的目光就移到了插入和删除上面，开始疑问，用 1 次 split 和 2 次 merge 插入一个结点真的是有必要的吗，删除一个结点要 2 次 split 和 3 次 merge 呢？光删除一个结点路径都要遍历 5 遍了。

自己想不出如何优化，便到 UOJ 交流群提问。一看到有人在发钱哥的博客，我想这一定是最优质的解答。

奈何当时对 Treap 还理解不深，一下看不懂便把博客丢进收藏夹里吃灰了，直到最近重新感悟了一遍 Treap 后它才重见天日。

钱哥的博客好深刻啊！深刻的原因之一是因为没有代码实现。尝试自己实现时调了不少时间不说，插入这部分我复杂度还写假了，最后还是在 UOJ 群友的帮助下才弄懂正确的写法。

钱哥太强了，跑得确实很快！但是实现确实有不少深刻的地方和坑点，再加上当时有些群友还是认为 FHQ-Treap 常数很大，于是就想写一篇博客，写一些对钱哥的博客自己的理解，并讲一些其他操作的更小常数操作的实现。为 FHQ-Treap 正名——常数可以不大，用法一点不少。

想感谢许多人对我学习平衡树过程中的帮助，鸣谢名单将会被放在这篇博客的最后一段。

开始前

在开始前，先确保你已经：

• 较为全面地了解了 Treap 基本的概念与性质
• 会用 FHQ-Treap 做 P6136
• 会用 FHQ-Treap 做 P2042

也就是会用 FHQ-Treap 维护值域和序列就可以了。

基础定义、符号与基本操作

既然准备好开始了，想必你对 FHQ-Treap 的基本操作已经了如指掌。但为了避免对一些变量名、符号的作用或基础操作的实现有分歧，这里附上我的写法与习惯并详细解释。

基础定义、符号

基础定义

template <typename Tp, size_t MAXN>
struct FHQ_Treap {
    using ui = unsigned;

    mt19937 rnd{20100601};
    struct Node {
        Tp val; ui prio, sz, ls, rs;
    } tree[MAXN + 1];
    ui root, cur, stk[MAXN + 1], top;

    FHQ_Treap() {
        root = {};
        cur = {};
        top = {};
        tree[0].sz = {};
    }

我们定义了一个模板结构体，Tp 为要维护的权值类型，MAXN 为同一时间最多同时存在的结点数量。

结构体内

• 所有代码使用 ui 为 unsigned 类型的别名

构造函数

• 将 root、cur、top 置 0。
• 将结点 0 维护的信息设为幺元。

符号

设 h 为当前 Treap 的树高。

基本操作

以下函数的实现较为基础，根据维护的信息的复杂程度代码可能会有所增改。

新建一个结点(newNode(Tp))

ui newNode(const Tp &val) {
    ui now = top ? stk[top--] : ++cur;
    tree[now] = {val, rnd(), 1, 0, 0};
    return now;
}

传入一个和此 Treap 维护的权值类型相同的权值 val。新建一个权值为 val 的结点，prio 为 rnd 新发生的一个随机数的结点。返回新建的结点的编号。

void pushup(ui)

void pushup(ui pos) {
    tree[pos].sz = tree[tree[pos].ls].sz + 1 + tree[tree[pos].rs].sz;
}

传入一个结点的编号 pos，将 pos 的左子树的信息与 pos 的信息复合再用此次复合的结果与 pos 的右子树的信息复合，得到 pos 为根的子树的信息。

void pushdown(ui)

void pushdown(ui pos);

传入一个结点的编号 pos，将 pos 的懒标记分别下放给它的左右子树。

按值域分裂(pair<ui, ui> splitRoot(ui, Tp) & pair<ui, ui> splitRoot_Strict(ui, Tp))

pair<ui, ui> splitRoot(ui pos, const Tp &key) {
    if (!pos) {
        return {};
    }

    if (tree[pos].val <= key) {
        auto [l, r] = splitRoot(tree[pos].rs, key);
        tree[pos].rs = l;
        pushup(pos);
        return {pos, r};
    }
    auto [l, r] = splitRoot(tree[pos].ls, key);
    tree[pos].ls = r;
    pushup(pos);
    return {l, pos};
}

传入一个结点的编号 pos 与和此 Treap 维护的类型相同的权值 key，将 pos 为根的子树分成维护的权值均 \leq key 的与 > key 的两棵 Treap。按顺序分别返回这两棵 Treap 的根的编号。

类似的，我们还有 splitRoot_Strict，除了是将 pos 为根的子树分成 < key 的与 \ge key 的两棵 Treap 以外作用与 splitRoot 毫无区别。

std::pair<ui, ui> splitRoot_Strict(ui pos, const Tp &key) {
    if (!pos) {
        return {};
    }
    if (tree[pos].val < key) {
        auto [l, r] = splitRoot_Strict(tree[pos].rs, key);
        tree[pos].rs = l;
        pushup(pos);
        return {pos, r};
    }
    auto [l, r] = splitRoot_Strict(tree[pos].ls, key);
    tree[pos].ls = r;
    pushup(pos);
    return {l, pos};
}

按大小分裂(ui splitRoot(ui, ui))

pair<ui, ui> splitRoot(ui pos, ui sz) {
    if (!pos) {
        return {};
    }

    if (sz <= tree[tree[pos].ls].sz) {
        auto [l, r] = splitRoot(tree[pos].ls, sz);
        tree[pos].ls = r;
        return {l, pos};
    }
    auto [l, r] = splitRoot(tree[pos].rs, sz - tree[tree[pos].ls].sz - 1);
    tree[pos].rs = l;
    pushup(pos);
    return {pos, r};
}

传入一个结点的编号 pos 与一个数字 sz，将 pos 为根的子树的中序遍历中的前 sz 个结点裂出，形成两棵 Treap。按顺序分别返回这两棵 Treap 的根的编号。

合并两棵 Treap(ui mergeRoot(ui, ui))

ui mergeRoot(ui l, ui r) {
    if (!l | !r) {
        return l | r;
    }
    if (tree[l].prio < tree[r].prio) {
        tree[l].rs = mergeRoot(tree[l].rs, r);
        pushup(l);
        return l;
    }
    tree[r].ls = mergeRoot(l, tree[r].ls);
    pushup(r);
    return r;
}

传入两个结点的编号 l 与 r，在不改变两棵 Treap 内部结点中序遍历的先后顺序的情况下，将 l 和 r 为根的 Treap 合并成一棵 Treap，使得以 r 为根的 Treap 的所有结点的中序遍历晚于以 l 为根的 Treap 的任意一个结点。返回合并后的 Treap 的树根编号。

主要操作

以上基本操作的实现较为平凡，但接下来有些操作要开始深刻起来了。

插入一个结点（值域）

这里讲一个方法： 假设随机值是小根堆，对于插入，我们比较随机值，如果随机值比树根小，就把这个树按照插入权值 split 开，然后当成插入节点的两个儿子。 不然我们就根据权值比较，进入对应子树继续插入。\ ——Treap, skip2004

一个正确的实现如下：

void insert(const Tp &val) {
    ui tar = newNode(val);
    auto dfs = [&](auto &&self, ui &pos) -> void {
        if (!pos) {
            pos = tar;
            return ;
        }
        if (tree[tar].prio < tree[pos].prio) {//我们比较随机值，如果随机值比树根小
            auto [l, r] = splitRoot_Strict(pos, val);//就把这个树按照插入权值 split 开
            tree[tar].ls = l; tree[tar].rs = r;//然后当成插入节点的两个儿子
            pos = tar;
        } else {
            self(self, tree[pos].val < val ? tree[pos].rs : tree[pos].ls);//不然我们就根据权值比较，进入对应子树继续插入。
        }
        pushup(pos);
    };
    dfs(dfs, root);
}

其实现了新建一个权值为 val 的结点并插入至合适位置。

时间复杂度为 O(h)。

一些深刻的正确性保证

这里有个深刻的细节问题：实现中的分裂为什么不可以使用 splitRoot？

在回答这个问题之前，我们先回顾一下 Treap 是什么。

Treap 是一棵笛卡尔树，而……

笛卡尔树是一种二叉树，每一个节点由一个键值二元组 (k,w) 构成。要求 k 满足二叉搜索树的性质，而 w 满足堆的性质。如果笛卡尔树的 k,w 键值确定，且 k 互不相同，w 也互不相同，那么这棵笛卡尔树的结构是唯一的。\ ——笛卡尔树，OI Wiki

看似在我的 Treap 的定义中，k 即为 val，w 即为 prio。

这段引用自 OI Wiki 的文字在告诉我们，并不是所有 val 满足二叉搜索树的性质，prio 满足二叉堆的性质的 Treap 都是一棵平衡的二叉搜索树。