FHQ-Treap学习笔记

# FHQ-Treap学习笔记 --- 如果你没有学过平衡树，先去这个博客[关于二叉查找树的一些事儿（bst详解，平衡树入门）](https://www.luogu.com.cn/blog/ztz11/pinghengshu-bst)简单学习一下，然后你可在这个博客[浅析Treap——平衡树](https://www.luogu.com.cn/blog/HOJQVFNA/qian-xi-treap-ping-heng-shu)先学习一下 Treap 的思想， 然后你就可以看这篇博客了。 可能有些人会怀疑 Treap 的时间复杂度的稳定性，事实上，Treap是最快的几种平衡树之一，我的这个[提交记录](https://www.luogu.com.cn/record/39451996)证明确实 Treap 很快，可能 splay 在这道题里也很快，那么建议你去看一下这个题[普通平衡树（数据加强版）](https://www.luogu.com.cn/problem/P6136)，你就会发现 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]` 分别表示这个点的权值，个数，左右儿子，和随机值。 下面是两个基础函数： ```cpp inline void pushup(int now) { siz[now] = siz[tr[now][0]] + siz[tr[now][1]] + 1; } ``` pushup操作是每个平衡树里都有的，但是这个不同的是，它只多加了 1，这是因为在 FHQ-Treap 中对于权值相同的点我们选择反复插入，而不是在一个点上记录个数。 ```cpp 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]$ 上的点分裂成右子树。 这样分裂的目的是为了可以在合并在一起，不要忘记我们必须满足平衡树的性质。  看这张我瓢过来的图片应该就可以看懂。 其实我并没有讲为什么这样分裂是正确的，这个有兴趣自己查吧。（其实很好理解的） 然后就是代码了： ```cpp 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 的原理很类似）  还是张图片。 **小贴士：左区间树与右区间树不能存在区间相交或顺序颠倒的情况** 代码： ```cpp 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]$ 两棵平衡树，然后把新加入的节点也看作一课平衡树，最后**依次**合并三棵平衡树就可以了。 ```cpp 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]$ 两个区间即可。 ```cpp split(rt, x, rt1, rt3), split(rt1, x-1, rt1, rt2); rt = merge(rt1, rt3); ``` 如果只删除一个，我们就只把 $[x, x]$ 的根节点删去即可。 ```cpp 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; ```cpp split(rt, x-1, rt1, rt2); printf("%d\n", siz[rt1] + 1); rt = merge(rt1, rt2); ``` ### 查询指定排名的一个数 这个只能暴力的往下找了，没别的好办法。 ```cpp 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] 的数即可，查询后继与查询前驱是类似的。 ```cpp 前驱 split(rt, x-1, rt1, rt2); printf("%d\n", val[kth(rt1, siz[rt1])]); rt = merge(rt1, rt2); ``` ```cpp 后继 split(rt, x, rt1, rt2); printf("%d\n", val[kth(rt2, 1)]); rt = merge(rt1, rt2); ``` 当然 FHQ-Treap 还有很多高级操作，可是我还没有学习，暂时先讲这么多吧。 ## 例题 [【模板】普通平衡树](https://www.luogu.com.cn/problem/P3369) 直接给份代码： ```cpp #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 还是快一些的。 [普通平衡树（数据加强版）](https://www.luogu.com.cn/problem/P6136) 这道题可以真正看出 FHQ-Treap 和 splay 的时间效率的差距，splay 跑了 14s, 而FHQ-Treap只跑了 7.6s，确实是快很多。 ## 总结 个人感觉 FHQ-Treap 既好理解又不容易错，时间效率很高，关键是代码具短。 打熟了之后大概10分钟就可以了。 而且 FHQ-Treap 扩展的功能很多，完全不弱于 splay。 好了，今天的讲解就到这里了。