FHQ-Treap学习笔记

· · 个人记录

FHQ-Treap学习笔记

如果你没有学过平衡树，先去这个博客关于二叉查找树的一些事儿（bst详解，平衡树入门）简单学习一下，然后你可在这个博客浅析Treap——平衡树先学习一下 Treap 的思想， 然后你就可以看这篇博客了。

可能有些人会怀疑 Treap 的时间复杂度的稳定性，事实上，Treap是最快的几种平衡树之一，我的这个提交记录证明确实 Treap 很快，可能 splay 在这道题里也很快，那么建议你去看一下这个题普通平衡树（数据加强版），你就会发现 Treap 比 splay 快一倍。

但是 Treap 最不好的一点是用处太少，它不能解决序列上的问题，比如文艺平衡树。所以很多人直接选择学习 splay，但是 FHQ-Treap 也可以解决文艺平衡树的问题，换句话说，基本上 splay 可以干的 FHQ-Treap 都能干。

而且它的速度也很快，反正比 splay 快多了。
最关键的是，它的代码量很小，我们都知道 splay 大概在 100 行左右，而 FHQ-Treap 却是在 50 行左右，码量小了一半，这样就使得在考场上可以用更少的时间写一个平衡树，而不是用 STL 里的 set。

本篇博客不会讲解的太深，大概主要讲解各种操作。

一些基础

我们规定 val[N], siz[N], tr[N][2], rd[N] 分别表示这个点的权值，个数，左右儿子，和随机值。
下面是两个基础函数： 

inline void pushup(int now) { siz[now] = siz[tr[now][0]] + siz[tr[now][1]] + 1; }

pushup操作是每个平衡树里都有的，但是这个不同的是，它只多加了 1，这是因为在 FHQ-Treap 中对于权值相同的点我们选择反复插入，而不是在一个点上记录个数。 

inline int new_node(int x) {
    val[++cnt] = x, siz[cnt] = 1, rd[cnt] = rand(); return cnt;
}

这个是建一个新点，与其它平衡树不同的是，它不需要管自己的左右儿子是谁。

核心操作1：分裂（split）

分裂操作非常好理解，就是把一个大的平衡树分裂为两个小的平衡树，实际上我们是按照区间进行分裂的，即假设值域为 [l, r]，我们规定一个值 val, 我们把 [l, val] 上的点分裂成左子树，把 [val + 1, r] 上的点分裂成右子树。

这样分裂的目的是为了可以在合并在一起，不要忘记我们必须满足平衡树的性质。

看这张我瓢过来的图片应该就可以看懂。
其实我并没有讲为什么这样分裂是正确的，这个有兴趣自己查吧。（其实很好理解的）

然后就是代码了： 

inline void split(int now, int p, int &x, int &y) {
    //如果当前访问节点为空，将左右区间树的虚拟节点赋值为0。
    if(now == 0) return x = 0, y = 0, void();
    //如果当前节点的val<=k则该节点与其左子树一并归入左区间树，在左区间树中对右儿子建立虚拟节点并继续分裂右子树。
    if(p >= val[now]) x = now, split(tr[now][1], p, tr[now][1], y);
    //如果当前节点的val>k则该节点与其右子树一并归入右区间树，在右区间树中对左儿子建立虚拟节点并继续分裂左子树。
    else y = now, split(tr[now][0], p, x, tr[now][0]); 
    pushup(now);
    //分裂完之后上传左右儿子的维护值至now节点，若now为空在先前就已经return。
}

注意别忘了取地址。
事实上，我们应该把根节点开成全局变量，与其他平衡树不一样的是，我们需要至少开三个根节点。

核心操作2：合并 (merge)

分裂是为了解决当前的问题，而合并是为了更好的解决下一个问题。

我们发现我们进行分裂操作的时候左右区间的交集是空集，这就为我们的合并提供了正确性。

具体来说，合并采用节点的随机值进行合并，每次把随机值小的当根节点，这样就保证了树的平衡（跟 Treap 的原理很类似）
还是张图片。
小贴士：左区间树与右区间树不能存在区间相交或顺序颠倒的情况 代码： 

inline int merge(int x, int y) {
    //如果有任意一个树为空就返回非空的一棵的根
    if(!x || !y) return x + y;
    if(rd[x] < rd[y]) {
        tr[x][1] = merge(tr[x][1], y), pushup(x); return x; 
    }
    else {
        tr[y][0] = merge(x, tr[y][0]), pushup(y); return y;
    }
}

感觉合并与线段树合并很像。

分裂与合并的应用

利用分裂合并我们可以做些什么呢？我们可以维护一个有序序列并支持插入、删除、查询指定排名的一个数、查询一个数的排名、前驱、后继等。

插入

设插入的权值为x，那么我们把平衡树分裂为 [l, x] 和 [x + 1, r] 两棵平衡树，然后把新加入的节点也看作一课平衡树，最后依次合并三棵平衡树就可以了。 

split(rt, x, rt1, rt2);
rt = merge(merge(rt1, new_node(x)), rt2);

删除

删除分两种，一种是把权值为 x 的节点全部删除，一种是只删除一个，其实这两个是差不多的。
我们首先分裂出 [l, x-1], [x, x] 和 [x+1, r] 三个区间。
如果全部删除，那没直接合并 [l, x-1] 和 [x+1, r] 两个区间即可。 

split(rt, x, rt1, rt3), split(rt1, x-1, rt1, rt2);  
rt = merge(rt1, rt3);

如果只删除一个，我们就只把 [x, x] 的根节点删去即可。 

split(rt, x, rt1, rt3), split(rt1, x-1, rt1, rt2);
rt2 = merge(tr[rt2][0], tr[rt2][1]);
rt = merge(merge(rt1, rt2), rt3);

查询某个数的排名

按照上面的思路，我们只需要把区间分裂为 [l, x-1] 和 [x, r]。
然后 x 的排名就是 siz[rt1] + 1; 

split(rt, x-1, rt1, rt2);
printf("%d\n", siz[rt1] + 1);
rt = merge(rt1, rt2);

查询指定排名的一个数

这个只能暴力的往下找了，没别的好办法。 

inline int kth(int now, int k) {
    while(1) {
        if(k <= siz[tr[now][0]]) now = tr[now][0];
        else if(k == siz[tr[now][0]] + 1) return now;
        else k -= siz[tr[now][0]] + 1, now = tr[now][1];
    }
}

查询前驱 与 后继

对于前驱我们把区间分裂为 [l, x-1] 和 [x, r]， 然后直接查询第一个区间排名为 siz[rt1] 的数即可，查询后继与查询前驱是类似的。

前驱
split(rt, x-1, rt1, rt2);
printf("%d\n", val[kth(rt1, siz[rt1])]);
rt = merge(rt1, rt2); 
后继
split(rt, x, rt1, rt2);
printf("%d\n", val[kth(rt2, 1)]);
rt = merge(rt1, rt2);

当然 FHQ-Treap 还有很多高级操作，可是我还没有学习，暂时先讲这么多吧。

例题

【模板】普通平衡树
直接给份代码： 

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
inline int read(int x = 0) { return scanf("%d", &x), x; }
int val[N], siz[N], tr[N][2], rd[N], rt, rt1, rt2, rt3, cnt;
inline void pushup(int now) { siz[now] = siz[tr[now][0]] + siz[tr[now][1]] + 1; }
inline int new_node(int x) {
    val[++cnt] = x, siz[cnt] = 1, rd[cnt] = rand(); return cnt;
} 
inline int merge(int x, int y) {
    if(!x || !y) return x + y;
    if(rd[x] < rd[y]) {
        tr[x][1] = merge(tr[x][1], y), pushup(x); return x; 
    }
    else {
        tr[y][0] = merge(x, tr[y][0]), pushup(y); return y;
    }
}
inline void split(int now, int p, int &x, int &y) {
    if(now == 0) return x = 0, y = 0, void();
    if(p >= val[now]) x = now, split(tr[now][1], p, tr[now][1], y); 
    else y = now, split(tr[now][0], p, x, tr[now][0]); 
    pushup(now);
}
inline int kth(int now, int k) {
    while(1) {
        if(k <= siz[tr[now][0]]) now = tr[now][0];
        else if(k == siz[tr[now][0]] + 1) return now;
        else k -= siz[tr[now][0]] + 1, now = tr[now][1];
    }
}
int main() {
    int n = read(), op, x;
    while(n--) {
        op = read(), x = read();
        switch(op) {
            case 1: split(rt, x, rt1, rt2);
                    rt = merge(merge(rt1, new_node(x)), rt2); break;
            case 2: split(rt, x, rt1, rt3), split(rt1, x-1, rt1, rt2);
                    rt2 = merge(tr[rt2][0], tr[rt2][1]), rt = merge(merge(rt1, rt2), rt3); break;
            case 3: split(rt, x-1, rt1, rt2), printf("%d\n", siz[rt1] + 1);
                    rt = merge(rt1, rt2); break;
            case 4: printf("%d\n", val[kth(rt, x)]); break;
            case 5: split(rt, x-1, rt1, rt2), printf("%d\n", val[kth(rt1, siz[rt1])]);
                    rt = merge(rt1, rt2); break;
            case 6: split(rt, x, rt1, rt2), printf("%d\n", val[kth(rt2, 1)]);
                    rt = merge(rt1, rt2); break;
        }       
    }
    return 0;
}

用时不算多，只有 300ms，比 splay 还是快一些的。

普通平衡树（数据加强版）
这道题可以真正看出 FHQ-Treap 和 splay 的时间效率的差距，splay 跑了 14s, 而FHQ-Treap只跑了 7.6s，确实是快很多。

总结

个人感觉 FHQ-Treap 既好理解又不容易错，时间效率很高，关键是代码具短。
打熟了之后大概10分钟就可以了。
而且 FHQ-Treap 扩展的功能很多，完全不弱于 splay。
好了，今天的讲解就到这里了。