介绍
fhqtreap为利用分裂和合并来满足平衡树的性质，不需要旋转操作的一种平衡树。
并且利用函数式编程可以极大的简化代码量。
（题目是抄唐神的来着）
核心操作
（均为按位置分裂合并）
struct fhq {
int lc, rc, siz, rnd, val;
//lc为左子树，rc为右子树，siz为子树大小（位置分裂即按siz分裂），rnd为随机值，val为该节点储存的值
}t[N];
#define lc (t[rt].lc)
#define rc (t[rt].rc)
//下方用到的宏定义split(rt,l,r,k) 把一个根为rt的子树split成一个根为l和一个根为r的子树(以第k大为界限)
void split(int rt, int &l, int &r, int k) {
if(!k) l = 0, r = rt;
else if(t[rt].siz == k) l = rt, r = 0;
else if(k <= t[lc].siz) r = rt, split(lc, l, lc, k), up(rt);
else l = rt, split(rc, rc, r, k - t[lc].siz - 1), up(rt);
}merge(rt,l,r) 把根为l和根为r的子树merge成一个根为rt的子树
merge默认子树l的权值比子树r的权值小
merge满足小根堆性质(对rnd)
void merge(int &rt, int l, int r) {
if(!l || !r) rt = l + r;
else if(t[l].rnd < t[r].rnd) rt = l, merge(rc, rc, r), up(rt);
else rt = r, merge(lc, l, lc), up(rt);
}fhqtreap也有一种按权值分裂的做法，但用处不大，如果要用位置分裂实现权值分裂，可以将序列构造成一个递增的序列，写一个rank求一下插入的数的在序列中的位置，插入到那里就行了（这样就能搞权值分裂能搞的东西了）、
区间操作打懒标记的话，在split和merge的时候下传即可。
常用操作
注意，当需要求max或者min的时候，一定要把root的max/min和val都设成inf/-inf
里面的sum即为上方提到的val。
建新节点
int build(int val) {
t[++tot].rnd = rand() << 15 | rand();
t[tot].siz = 1;
t[tot].sum = val;
return tot;
}查排名（上方提到的rank，这个是\(logn\)的）
int rank(int rt, int val) {
if(!rt) return 0;
if(t[rt].sum == val) return t[lc].siz + 1;
if(t[rt].sum > val) return rank(lc, val);
return rank(rc, val) + t[lc].siz + 1;
}插入
inline void insert(int val) {
int rk = rank(root, val), x, y;
split(root, x, y, rk);
int z = build(val);
merge(x, x, z); merge(root, x, y);
}删除
inline void del(int val) {
int rk = rank(root, val) + 1, x, y, z;
split(root, x, y, rk);
split(x, x, z, rk - 1);
merge(root, x, y);
}其他操作均类似。
要注意的一个问题：merge和split均针对的是根为rt的子树，所以对应的k也是他们子树中的第k大。可以看看下面的代码。
inline int find(int rk) {//找排名为rk的数
int x, y, z, ans;
split(root, x, y, rk - 1);
split(y, y, z, 1);
ans = t[y].sum;
merge(y, y, z); merge(root, x, y);
return ans;
/*
split(root, x, y, rk); split(x, z, x, rk - 1);
ans = t[x].sum;
merge(x, z, x), merge(root, x, y);
return ans;
*/
}即在一整个根为root的树中找第rk大，可以有两种实现：1.分裂成前rk大和剩下的，并将前rk大分裂成rk-1大和第rk大。2.分裂成前rk-1大和剩下的，将剩下的那部分，分裂成第一大（不要弄成rk+1!）和后面的
模板题
LuoguP3369 【模板】普通平衡树
就是平衡树的常见操作，可以直接写权值分裂，也可以写位置分裂（构造成递增数列）
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <queue>
#include <ctime>
#include <cmath>
#include <stack>
#include <deque>
#include <map>
#include <set>
#define ll long long
const int inf = 2e9 + 10;
typedef unsigned long long ull;
namespace io {
#define in(a) a = read()
#define out(a) write(a)
#define outn(a) out(a), putchar('\n')
#define I_int int
inline I_int read() {
I_int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
char F[200];
inline void write(I_int x) {
if (x == 0) return (void) (putchar('0'));
I_int tmp = x > 0 ? x : -x;
if (x < 0) putchar('-');
int cnt = 0;
while (tmp > 0) {
F[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while (cnt > 0) putchar(F[--cnt]);
}
#undef I_int
}
using namespace io;
using namespace std;
#define N 500010
#define lc (t[rt].l)
#define rc (t[rt].r)
struct fhq {
int l, r, sum, siz, rnd;
} t[N];
int tot = 0, root = 0;
void up(int rt) {
if(!rt) return;
t[rt].siz = 1 + t[lc].siz + t[rc].siz;
}
void split(int rt, int &l, int &r, int k) {
//把根为rt的子树，以第k个为界限split成两个子树
//第k个可以是位置，也可以是权值
//这里的k是位置
if(!k) l = 0, r = rt;
else if(k == t[rt].siz) l = rt, r = 0;
else if(k <= t[lc].siz) r = rt, split(lc, l, lc, k), up(rt);
else l = rt, split(rc, rc, r, k - t[lc].siz - 1), up(rt);
}
void merge(int &rt, int l, int r) {
//把l子树和r子树merge为一棵根为rt的子树
if(!l || !r) rt = l + r;
else if(t[l].rnd < t[r].rnd) rt = l, merge(t[rt].r, t[rt].r, r), up(rt);
else rt = r, merge(t[rt].l, l, t[rt].l), up(rt);
}
int build(int val) {
t[++tot].rnd = rand() << 15 | rand();
t[tot].siz = 1;
t[tot].sum = val;
return tot;
}
int rank(int rt, int val) {
if(!rt) return 0;
if(t[rt].sum >= val) return rank(lc, val);
return rank(rc, val) + t[lc].siz + 1;
}
inline void insert(int val) {
int rk = rank(root, val), x, y;
split(root, x, y, rk);
int z = build(val);
merge(x, x, z); merge(root, x, y);
}
inline void del(int val) {
int rk = rank(root, val) + 1, x, y, z;
split(root, x, y, rk);
split(x, x, z, rk - 1);
merge(root, x, y);
}
inline int find(int rk) {
int x, y, z, ans;
split(root, x, y, rk - 1);
split(y, y, z, 1);
ans = t[y].sum;
merge(y, y, z); merge(root, x, y);
return ans;
/*
split(root, x, y, rk); split(x, z, x, rk - 1);
ans = t[x].sum;
merge(x, z, x), merge(root, x, y);
return ans;
*/
}
inline int pre(int val) {
int x, y, z, ans, rk = rank(root, val);
split(root, x, y, rk);
split(x, z, x, rk - 1);
ans = t[x].sum;
merge(x, z, x); merge(root, x, y);
return ans;
}
inline int succ(int val) {
int x, y, z, ans, rk = rank(root, val + 1);
split(root, x, y, rk + 1); split(x, z, x, rk);
ans = t[x].sum;
merge(x, z, x); merge(root, x, y);
return ans;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
#endif
srand((unsigned)time(0));
t[0].rnd = t[0].sum = inf;
int n = read();
for(int i = 1; i <= n; ++i) {
int op = read(), x = read();
if(op == 1) insert(x);
if(op == 2) del(x);
if(op == 3) printf("%d\n", rank(root, x) + 1);
if(op == 4) printf("%d\n", find(x));
if(op == 5) printf("%d\n", pre(x));
if(op == 6) printf("%d\n", succ(x));
}
}例题
LuoguP2161 [SHOI2009]会场预约
BZOJ1861: [Zjoi2006]Book 书架
BZOJ1251: 序列终结者
POJ3580 SuperMemo
京公网安备 11010502036488号