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);
	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;
	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);
	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);
    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("%lld\n", t[t2].sum);
            rt = Merge(Merge(t1, t2), t3);
        }
        if (op == "MAX-SUM") {
            printf("%lld\n", 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("%d\n", getrank(x));
            break ;
        case 4 :
            printf("%d\n", getval(x));
            break ;
        case 5 :
            printf("%d\n", pre(x));
            break ;
        case 6 :
            printf("%d\n", las(x));
            break ;
        }
    }
    return 0;
}