FHQ-treap，即无旋 treap，又称分裂合并 treap，支持维护序列，可持久化等特性。
FHQ-treap 有两个核心操作，分裂 与 合并。通过这两个操作，在很多情况下可以比旋转 treap 等方便的实现一些操作。
FHQ-treap 与其他的平衡树相比，他最明显的优点是：它好写！！！，想象一下，在考场上，你用较短的时间写出 FHQ-treap 和花很长时间敲 Splay，还得琢磨到底怎么旋转，优势就体现的很明显了，它和 treap 相比，它可以更好的进行区间操作，接下来将一一介绍。
平衡树也是一棵二叉搜索树。
结构体定义
定义
这里我们采取结构体来定义平衡树的节点，下面是最基本的节点信息。
struct node { int val, pai, siz; int ls, rs; } t[N]; pai 是我们随机的一个值，val 是当前节点的权值，ls, rs 左右孩子，siz 是当前点的子树大小。
增加新节点
为了节省空间，我们一般会开一个“垃圾桶”来存储被删掉的节点的编号，要增加新节点时，如果垃圾桶里有节点，那么优先使用垃圾桶里的节点。回收利用很环保
vector<int> rub; int newnod(int x) { int u; if (!rub.empty()) { u = rub.back(); rub.pop_back(); } else { u = ++ tot; } t[u].siz = 1; t[u].ls = t[u].rs = 0; t[u].val = x; t[u].pai = rand(); return u; } 分裂
分裂有两种，一种是按照节点个数来分裂，另一种是按照权值大小来分裂。
一般最常用的是按照节点个数分裂，但是按照权值大小分裂也会用到。
一般进行操作，我们的通用方法是将被操作点单独分裂成一棵树，对这棵树进行操作。
按照节点数量分裂的代码。
void split_rk(int u, int k, int &x, int &y) { if (u == 0) { x = y = 0; return ; } if (t[lc].siz + 1 <= k) { x = u; split_rk(rc, k - t[lc].siz - 1, t[u].rs, y); } else { y = u; split_rk(lc, k, x, t[u].ls); } pushup(u); } 按照权值分裂的代码。
void split_val(int u, int v, int &x, int &y) { // x 和 y 是传参类型 if (u == 0) { x = y = 0; return ; } if (t[u].val <= v) { x = u; split_val(rc, v, rc, y); } else { y = u; split_val(lc, v, x, lc); } pushup(u); } 合并
在旋转 treap 中，我们借助旋转操作来维护堆的性质，同时旋转时还不能改变树的性质。在无旋 treap 中，我们用合并达到相同的效果。
因为两个 treap 已经有序，所以我们在合并的时候只需要考虑把哪个树「放在上面」，把哪个「放在下面」，也就是是需要判断将哪个一个树作为子树。显然，根据堆的性质，我们需要把 (pai) 小的放在上面（这里采用小根堆）。
同时，我们还需要满足搜索树的性质。设 (u < v)，若 (u) 的 (pai) 小于 (v) 的，那么 (u) 即为新根结点，并且 (v) 因为值比 (u) 更大，应与 (u) 的右子树合并；反之，则 (v) 作为新根结点，然后因为 (u) 的值比 (v) 小，与 (v) 的左子树合并。
int Merge(int x, int y) { if (!x || !y) { return x + y; } if (t[x].pai < t[y].pai) { t[x].rs = Merge(t[x].rs, y); pushup(x); return x; } else { t[y].ls = Merge(x, t[y].ls); pushup(y); return y; } } 基本操作
插入
将新节点要插入的位置分裂出来，然后合并即可。
void Insert(int x) { int u = newnod(x); int t1, t2; split_val(rt, x, t1, t2); rt = Merge(Merge(t1, u), t2); } 删除
将要删除的节点分裂出来，将两边的子树合并即可。
void Erase(int x) { int t1, t2, t3; split_val(rt, x - 1, t1, t2); split_val(t2, x, t2, t3); rub.emplace_back(t2); t2 = Merge(t[t2].ls, t[t2].rs); rt = Merge(Merge(t1, t2), t3); } 查找排名
将要查找的点按照权值分裂出来，前面分裂出去的树的大小 (+ 1) 就是排名。
int getrank(int x) { int t1, t2, rk; split_val(rt, x - 1, t1, t2); rk = t[t1].siz + 1; rt = Merge(t1, t2); ans ^= rk; las = rk; return rk; } 查找排名为 (x) 的节点的权值
将要查找的点按照节点个数分裂出来，进行操作。
int getval(int x) { int t1, t2, t3, val; split_rk(rt, x - 1, t1, t2); split_rk(t2, 1, t2, t3); val = t[t2].val; ans ^= val; las = val; Merge(Merge(t1, t2), t3); return val; } 查找前驱后继
利用分裂来查找。
int pre(int x) { int t1, t2, t3, pre; split_val(rt, x - 1, t1, t2); split_rk(t1, t[t1].siz - 1, t1, t3); pre = t[t3].val; rt = Merge(Merge(t1, t3), t2); ans ^= pre; las = pre; return pre; } int nxt(int x) { int t1, t2, t3, nxt; split_val(rt, x, t1, t2); split_rk(t2, 1, t2, t3); nxt = t[t2].val; rt = Merge(Merge(t1, t2), t3); ans ^= nxt; las = nxt; return nxt; } 区间操作
P3391 【模板】文艺平衡树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
区间翻转练习题
/* The code was written by yifan, and yifan is neutral!!! */ #include <bits/stdc++.h> using namespace std; typedef long long ll; #define lc t[u].ls #define rc t[u].rs template<typename T> inline T read() { T x = 0; bool fg = 0; char ch = getchar(); while (ch < '0' || ch > '9') { fg |= (ch == '-'); ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); } return fg ? ~x + 1 : x; } const int N = 1e5 + 5; int n, m, rt, tot; vector<int> rub; struct node { int val, tag; int ls, rs, siz, pai; } t[N << 1]; inline void pushup(int u) { t[u].siz = t[lc].siz + t[rc].siz + 1; } inline void pushdown(int u) { if (!t[u].tag) { return ; } if (lc) t[lc].tag ^= 1; if (rc) t[rc].tag ^= 1; swap(t[u].ls, t[u].rs); t[u].tag = 0; } int newnod(int x) { int u = ++ tot; t[u].siz = 1; t[u].ls = t[u].rs = t[u].tag = 0; t[u].val = x; t[u].pai = rand(); return u; } void split_rk(int u, int k, int &x, int &y) { if (!u) { x = y = 0; return ; } pushdown(u); if (t[lc].siz + 1 <= k) { x = u; split_rk(rc, k - t[lc].siz - 1, rc, y); } else { y = u; split_rk(lc, k, x, lc); } pushup(u); } int Merge(int x, int y) { if (!x || !y) { return x + y; } if (t[x].pai < t[y].pai) { pushdown(x); t[x].rs = Merge(t[x].rs, y); pushup(x); return x; } else { pushdown(y); t[y].ls = Merge(x, t[y].ls); pushup(y); return y; } } void print(int u) { if (!u) return ; pushdown(u); print(t[u].ls); printf("%d ", t[u].val); print(t[u].rs); } int main() { srand(time(NULL)); n = read<int>(), m = read<int>(); for (int i = 1; i <= n; ++ i) { rt = Merge(rt, newnod(i)); } for (int i = 1, l, r; i <= m; ++ i) { l = read<int>(), r = read<int>(); int t1, t2, t3; split_rk(rt, l - 1, t1, t2); split_rk(t2, r - l + 1, t2, t3); t[t2].tag ^= 1; rt = Merge(t1, Merge(t2, t3)); } print(rt); return 0; } P2042 [NOI2005] 维护数列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
区间操作的练习好题，涉及线段树操作。
/* The code was written by yifan, and yifan is neutral!!! */ #include <bits/stdc++.h> using namespace std; typedef long long ll; #define lc (t[u].ls) #define rc (t[u].rs) template<typename T> inline T read() { T x = 0; bool fg = 0; char ch = getchar(); while (ch < '0' || ch > '9') { fg |= (ch == '-'); ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); } return fg ? ~x + 1 : x; } const int N = 1e6 + 6; mt19937 rnd(time(0)); int n, m, tot, rt; int a[N]; vector<int> rub; struct node { int pai, ls, rs, siz; ll val, sum, mx, maxpre, maxlas, tag; bool tag1, tag2; } t[N]; int New(int x) { int u; if (!rub.empty()) { u = rub.back(); rub.pop_back(); } else { u = ++ tot; } t[u].sum = t[u].val = (t[u].mx = x); t[u].maxpre = t[u].maxlas = max(0, x); t[u].siz = 1; t[u].pai = rnd(); t[u].tag1 = t[u].tag2 = (t[u].tag = 0); t[u].ls = t[u].rs = 0; return u; } void pushup(int u) { if (!u) return; t[u].siz = t[lc].siz + t[rc].siz + 1; t[u].sum = t[lc].sum + t[rc].sum + t[u].val; t[u].maxpre = max(max(t[lc].maxpre, t[lc].sum + t[u].val + t[rc].maxpre), 0ll); t[u].maxlas = max(max(t[rc].maxlas, t[rc].sum + t[u].val + t[lc].maxlas), 0ll); t[u].mx = max(0ll, t[lc].maxlas + t[rc].maxpre) + t[u].val; if (lc) t[u].mx = max(t[u].mx, t[lc].mx); if (rc) t[u].mx = max(t[u].mx, t[rc].mx); } void cover(int u, ll c) { t[u].val = t[u].tag = c; t[u].sum = t[u].siz * c; t[u].maxpre = t[u].maxlas = max(0ll, t[u].sum); t[u].mx = max(c, t[u].sum); t[u].tag1 = 1; } void Reverse(int u) { if (!u) return ; swap(lc, rc); swap(t[u].maxpre, t[u].maxlas); t[u].tag2 ^= 1; } void pushdown(int u) { if (!u) return ; if (t[u].tag2) { if (lc) { Reverse(lc); } if (rc) { Reverse(rc); } t[u].tag2 = 0; } if (t[u].tag1) { if (lc) { cover(lc, t[u].tag); } if (rc) { cover(rc, t[u].tag); } t[u].tag = t[u].tag1 = 0; } } void split(int u, int k, int &x, int &y) { if (!u) { x = y = 0; return; } pushdown(u); if (t[lc].siz < k) { x = u; split(rc, k - t[lc].siz - 1, rc, y); } else { y = u; split(lc, k, x, lc); } pushup(u); } int Merge(int x, int y) { if (!x || !y) { return x + y; } if (t[x].pai < t[y].pai) { pushdown(x); t[x].rs = Merge(t[x].rs, y); pushup(x); return x; } else { pushdown(y); t[y].ls = Merge(x, t[y].ls); pushup(y); return y; } } int add(int l, int r) { if (l != r) { int mid = (l + r) >> 1; return Merge(add(l, mid), add(mid + 1, r)); } return New(a[l]); } void Erase(int u) { if (!u) return ; rub.emplace_back(u); if (lc) { Erase(lc); } if (rc) { Erase(rc); } } void print(int u) { if (!u) return ; pushdown(u); print(lc); print(rc); } int main() { n = read<int>(), m = read<int>(); for (int i = 1; i <= n; ++ i) { a[i] = read<int>(); } rt = Merge(rt, add(1, n)); string op; for (int i = 1, t1, t2, t3; i <= m; ++ i) { cin >> op; if (op == "INSERT") { int pos = read<int>(), len = read<int>(); split(rt, pos, t1, t2); for (int i = 1; i <= len; ++ i) { a[i] = read<int>(); } rt = Merge(Merge(t1, add(1, len)), t2); } if (op == "DELETE") { int pos = read<int>(), len = read<int>(); split(rt, pos - 1, t1, t2); split(t2, len, t2, t3); Erase(t2); rt = Merge(t1, t3); } if (op == "MAKE-SAME") { int pos = read<int>(), len = read<int>(), v = read<int>(); split(rt, pos - 1, t1, t2); split(t2, len, t2, t3); cover(t2, v); rt = Merge(Merge(t1, t2), t3); } if (op == "REVERSE") { int pos = read<int>(), len = read<int>(); split(rt, pos - 1, t1, t2); split(t2, len, t2, t3); Reverse(t2); rt = Merge(Merge(t1, t2), t3); } if (op == "GET-SUM") { int pos = read<int>(), len = read<int>(); split(rt, pos - 1, t1, t2); split(t2, len, t2, t3); printf("%lldn", t[t2].sum); rt = Merge(Merge(t1, t2), t3); } if (op == "MAX-SUM") { printf("%lldn", t[rt].mx); } } return 0; } P2596 [ZJOI2006] 书架 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
模板题
/* The code was written by yifan, and yifan is neutral!!! */ #include <bits/stdc++.h> using namespace std; typedef long long ll; #define lc t[u].ls #define rc t[u].rs template<typename T> inline T read() { T x = 0; bool fg = 0; char ch = getchar(); while (ch < '0' || ch > '9') { fg |= (ch == '-'); ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); } return fg ? ~x + 1 : x; } const int N = 8e4 + 5; mt19937 rnd(time(0)); int n, m, tot, rt; int Id[N]; struct node { int val, siz, pai; int ls, rs, fa; } t[N << 1]; void pushup(int u) { t[u].siz = t[lc].siz + t[rc].siz + 1; t[lc].fa = t[rc].fa = u; } int New(int x) { int u = ++ tot; t[u].siz = 1; t[u].val = x; t[u].pai = rnd(); t[u].ls = t[u].rs = t[u].fa = 0; Id[x] = u; return u; } int Find(int u) { int res = t[t[u].ls].siz + 1; for (; u != rt; u = t[u].fa) { if (t[t[u].fa].rs == u) { res += t[t[t[u].fa].ls].siz + 1; } } return res; } void split_rk(int u, int k, int &x, int &y) { if (!u) { x = y = 0; return ; } if (t[lc].siz < k) { x = u; split_rk(rc, k - t[lc].siz - 1, rc, y); } else { y = u; split_rk(lc, k, x, lc); } pushup(u); } int Merge(int x, int y) { if (!x || !y) { return x + y; } if (t[x].pai < t[y].pai) { t[x].rs = Merge(t[x].rs, y); pushup(x); return x; } else { t[y].ls = Merge(x, t[y].ls); pushup(y); return y; } } int main() { n = read<int>(), m = read<int>(); for (int i = 1; i <= n; ++ i) { rt = Merge(rt, New(read<int>())); } for (int i = 1, x, t1, t2, t3, t4; i <= m; ++ i) { string op; cin >> op; x = read<int>(); if (op == "Top") { int k = Find(Id[x]); split_rk(rt, k - 1, t1, t2); split_rk(t2, 1, t2, t3); rt = Merge(Merge(t2, t1), t3); } if (op == "Bottom") { int k = Find(Id[x]); split_rk(rt, k - 1, t1, t2); split_rk(t2, 1, t2, t3); rt = Merge(Merge(t1, t3), t2); } if (op == "Insert") { int y = read<int>(); int k = Find(Id[x]); if (y > 0) { split_rk(rt, k - 1, t1, t2); split_rk(t2, 1, t2, t3); split_rk(t3, y, t3, t4); rt = Merge(Merge(t1, t3), Merge(t2, t4)); } else { split_rk(rt, k - 1, t1, t2); split_rk(t2, 1, t2, t3); split_rk(t1, k + y - 1, t1, t4); rt = Merge(Merge(t1, t2), Merge(t4, t3)); } } if (op == "Ask") { cout << Find(Id[x]) - 1 << 'n'; } if (op == "Query") { split_rk(rt, x - 1, t1, t2); split_rk(t2, 1, t2, t3); cout << t[t2].val << 'n'; rt = Merge(Merge(t1, t2), t3); } } return 0; } P3369 【模板】普通平衡树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
/* The code was written by yifan, and yifan is neutral!!! */ #include <bits/stdc++.h> using namespace std; typedef long long ll; #define lc t[u].ls #define rc t[u].rs template<typename T> inline T read() { T x = 0; bool fg = 0; char ch = getchar(); while (ch < '0' || ch > '9') { fg |= (ch == '-'); ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); } return fg ? ~x + 1 : x; } const int N = 2e5 + 5; int n, tot, top, rt; vector<int> rub; struct node { int val, pai, siz; int ls, rs; } t[N]; inline int newnod(int x) { int u; if (!rub.empty()) { u = rub.back(); rub.pop_back(); } else { u = ++ tot; } t[u].siz = 1; t[u].ls = t[u].rs = 0; t[u].val = x; t[u].pai = rand(); return u; } inline void pushup(int u) { t[u].siz = t[lc].siz + 1 + t[rc].siz; } void split_rk(int u, int k, int &x, int &y) { if (u == 0) { x = y = 0; return ; } if (t[lc].siz + 1 <= k) { x = u; split_rk(rc, k - t[lc].siz - 1, t[u].rs, y); } else { y = u; split_rk(lc, k, x, t[u].ls); } pushup(u); } void split_val(int u, int v, int &x, int &y) { if (u == 0) { x = y = 0; return ; } if (t[u].val <= v) { x = u; split_val(rc, v, rc, y); } else { y = u; split_val(lc, v, x, lc); } pushup(u); } int Merge(int x, int y) { if (!x || !y) { return x + y; } if (t[x].pai < t[y].pai) { t[x].rs = Merge(t[x].rs, y); pushup(x); return x; } else { t[y].ls = Merge(x, t[y].ls); pushup(y); return y; } } inline void Insert(int x) { int u = newnod(x); int t1, t2; split_val(rt, x, t1, t2); rt = Merge(Merge(t1, u), t2); } inline void Erase(int x) { int t1, t2, t3; split_val(rt, x - 1, t1, t2); split_val(t2, x, t2, t3); rub.emplace_back(t2); t2 = Merge(t[t2].ls, t[t2].rs); rt = Merge(Merge(t1, t2), t3); } inline int getrank(int x) { int t1, t2, rk; split_val(rt, x - 1, t1, t2); rk = t[t1].siz + 1; rt = Merge(t1, t2); return rk; } inline int getval(int x) { int t1, t2, t3, val; split_rk(rt, x - 1, t1, t2); split_rk(t2, 1, t2, t3); val = t[t2].val; Merge(Merge(t1, t2), t3); return val; } inline int pre(int x) { int t1, t2, t3, pre; split_val(rt, x - 1, t1, t2); split_rk(t1, t[t1].siz - 1, t1, t3); pre = t[t3].val; rt = Merge(Merge(t1, t3), t2); return pre; } inline int las(int x) { int t1, t2, t3, las; split_val(rt, x, t1, t2); split_rk(t2, 1, t2, t3); las = t[t2].val; rt = Merge(Merge(t1, t2), t3); return las; } int main() { n = read<int>(); for (int i = 1, x, op; i <= n; ++ i) { op = read<int>(), x = read<int>(); switch(op) { case 1 : Insert(x); break ; case 2 : Erase(x); break ; case 3 : printf("%dn", getrank(x)); break ; case 4 : printf("%dn", getval(x)); break ; case 5 : printf("%dn", pre(x)); break ; case 6 : printf("%dn", las(x)); break ; } } return 0; } 
