我的算法书 - FHQ Treap：用分裂与合并维护有序集合

一句话算法

FHQ Treap 把所有平衡树操作拆成两件事：按条件切开 split，再按顺序拼回 merge。

问题模型

维护一个动态有序集合，支持：

插入一个值；
删除一个值；
查询排名；
查询第 $k$ 小；
查询前驱、后继。

普通 Treap 通过旋转恢复平衡；FHQ Treap 不旋转，而是依靠随机优先级和 split/merge 重组树。

核心直觉

一棵 FHQ Treap 同时满足：

中序遍历按值有序；
随机优先级满足堆性质。

split(root, v, x, y) 的含义是：

x 里所有值 <= v；
y 里所有值 > v。

merge(x, y) 的前提是：

x 中所有值都不大于 y 中所有值。

只要能切开和拼回，其他操作就变成组合题：

插入 v：split(root, v) -> A, B
       root = merge(merge(A, new(v)), B)

删除 v：split(root, v) -> A, C
       split(A, v - 1) -> A, B
       丢掉 B 的一个根，再 merge 回去

算法步骤

Split

对当前根 u：

如果 u 为空，两个结果都是空树。
如果 val[u] <= v，那么 u 和左子树一定属于左边结果。
右子树可能一部分 <= v，一部分 > v，递归分裂右子树。
如果 val[u] > v，对称处理左子树。
回溯时更新 size。

Merge

合并两棵树 x 和 y：

如果有一棵为空，返回另一棵。
比较根节点随机优先级。
优先级更高的根作为新根。
递归合并它的一侧子树。
回溯时更新 size。

常见操作

插入：

split(root, v, x, y)
root = merge(merge(x, new_node(v)), y)

删除一个 v：

split(root, v, x, z)
split(x, v - 1, x, y)
y = merge(left(y), right(y))
root = merge(merge(x, y), z)

排名和第 $k$ 小可以用 split 写，也可以直接按 BST 方式走树；模板里两种思路都有体现。

算法证明

核心不变量：每次操作后，树仍然满足 BST 顺序和堆优先级。

Split 正确性

直觉模型：给整棵树染色，<= v 染成左边，> v 染成右边。BST 的有序性保证每次只需要递归一侧。

若 u 为空，结论显然成立。
若 val[u] <= v：
- u 和左子树都应进入左边；
- 右子树可能混合两种颜色，所以递归分裂右子树；
- 分裂出的左半接回 u.right，仍然大于 u，BST 不变。
若 val[u] > v，对称处理左子树。
分裂只在原来的父子关系附近断边、接边；接回来的子树仍来自原子树，因此不会破坏堆性质。

所以 split 得到的两棵树值域正确，并且仍是合法 Treap。

Merge 正确性

前提是左树所有值都不大于右树所有值。

若一棵为空，返回另一棵，显然正确。
否则选优先级更高的根作为新根，堆性质成立。
如果选 x 为根，只需要合并 x.right 和 y；它们仍满足“左边值不大于右边值”的前提。
递归完成后，中序顺序仍是 x 的左侧、x、合并后的右侧，所以 BST 性质成立。

因此 merge 正确，所有由 split/merge 组合出的操作也正确。

复杂度分析

设集合大小为 $n$ 。

split、merge 的期望时间复杂度是 $O(\log n)$ 。
插入、删除、排名、第 $k$ 小、前驱、后继的期望时间复杂度都是 $O(\log n)$ 。
空间复杂度是 $O(n)$ 。

代码实现

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300

        #include <cstdio>
#include <random>
#include <limits>

template<typename T = long long,int N = 500005>
struct FHQ
{

    // ============ 数据
    int root;

    struct Node { 
        int l,r;
        int size,fix;
        T val;
    };
    // 使用内存池 替代
    Node tr[N];
    int tr_idx = 0;
    int get() { return ++tr_idx;}

    std::mt19937 rnd;
    // ============ 数据
    // 定义极值，用于表示“没找到”
    // 如果是 long long 题目，请确保 T 是 long long
    const T INF_MAX = std::numeric_limits<T>::max();
    const T INF_MIN = std::numeric_limits<T>::min();

    // ============ 构造函数
    FHQ() {
        // root = 0;
        rnd.seed(233);
        // 也可以用下面的方式初始化随机数种子
        // rnd.seed(std::random_device()());
        init();
    }

    // --- 1. 多组数据必备 (Clear & Init) ---
    
    void init() {
        root = 0;
        tr_idx = 0;
        // 哨兵清理：防止 tr[0] 脏数据污染 size 计算
        tr[0].l = tr[0].r = tr[0].size = 0; 
        tr[0].val = 0;
    }

    void clear() {
        init();
    }

    int size() const {
        return tr[root].size;
    }
    
    bool empty() const {
        return size() == 0;
    }

    // ============ 核心操作

    int new_node(T v) {
        int id = get();
        // tr[idx].ch[0]  = tr[idx].ch[1] = 0;
        tr[id].l = tr[id].r = 0; // 与上面等价
        tr[id].size = 1;
        tr[id].fix = rnd();
        tr[id].val = v;
        return id;
    }

    void update(int u ) {
        int l = tr[u].l;
        int r = tr[u].r;
        tr[u].size = tr[l].size + tr[r].size + 1;
    }

    // --- 这里的两个函数是 FHQ-Treap 的灵魂 ---

    /**
     * 分裂 (Split) - 按数值 v 分裂
     * 含义：将树 u 切成两棵树 x 和 y。
     * 功能: 
     *      1. 使得 x 指向 u 中所有节点值 <= v 的节点组成的树
     *      2. 使得 y 指向 u 中所有节点值 > v 的节点组成的树
     * x 树：所有节点值 <= v
     * y 树：所有节点值 > v
     * 注意：x 和 y 是通过引用传回的
     * 注: 经过我的各种写法,发现最好的写法就是下面的这个,不要在修改了 by rainboy 2025-11-17
     */
    void split(int u,int v,int &x,int &y) {
        // 边界: 如果 u 是空树，那么 x 和 y 都是空树
        if( !u ) { x = y = 0; return; }
        if( tr[u].val <= v ) {
            x = u;
            // 剩下的问题是：u 的右子树里，可能还有 <= v 的，也可能有一部分 > v 的
            // 所以我们递归处理 u 的右子树
            split(tr[u].r,v,tr[u].r,y);
        } else {
            // 当前节点 > v，说明当前节点及其右子树都属于 y
            y = u;
            // 递归处理 u 的左子树
            split(tr[u].l,v,x,tr[u].l);
        }
        update(u); // 更新 u 的 size , 因为 u 的左右子树可能发生了变化
    }

    /**
     * 合并 (Merge)
     * 含义：将两棵树 x 和 y 合并成一棵树，并返回新根。
     * 前提：x 中所有节点的值 必须 <= y 中所有节点的值 (即有序)
     * 技巧：利用随机优先级 pri 来决定谁做父节点，从而保持平衡
     */
    int merge(int x,int y) {
        // 边界其中一个是空树,空树是单位元:如果有一棵树是空的，那么合并结果就是另一棵树
        if( !x || !y ) return x + y; 

        // 谁的优先级高，谁就做父节点(取决于你是大根堆还是小根堆，这里用大根堆)
        if( tr[x].fix > tr[y].fix ) {
            tr[x].r = merge(tr[x].r,y);
            update(x); // 更新 x 的 size , 因为 x 的右子树可能发生了变化
            return x;
        } else {
            tr[y].l = merge(x,tr[y].l);
            update(y);
            return y;
        }
    }

    // --- 常用操作封装 (心智负担最低的写法) ---

    /**
     * 插入 (Insert)
     * 含义：将值 v 插入到树中
     * 注: 这个是最好的插入, 如果使用BST的插入,需要旋转,那就是普通Treap
     */
    void insert(T v) {
        int x,y;
        // 先按 v 分裂，把树切成 (<=v) 和 (>v) 两部分
        // 注: split <=v ,因为 新的节点放到相同的v的后面
        split(root,v,x,y);
        root = merge(merge(x,new_node(v)),y);
    }

    /**
     * 删除 (Delete)
     * 含义：将值 v 从树中删除
     * 注: 这个是最好的删除, 与插入一样
     */
    void del(T v) {
        int x, y, z;
        // 1. 把树按 v 分裂 -> x(<=v), z(>v)
        split(root, v, x, z);
        // 2. 把 x 按 v-1 分裂 -> x(<v), y(==v)
        split(x, v - 1, x, y);

        // 此时 y 树里全是值为 v 的节点。
        // 如果要删除所有 v，直接忽略 y 即可。
        // 如果只删除一个 v：
        if (y) // y不是空树
        {
            // 合并 y 的左右孩子，相当于把 y 的根节点丢弃了
            y = merge(tr[y].l, tr[y].r);
        }

        // 3. 全部装回去
        root = merge(merge(x, y), z);
    }

    /**
     * 查询排名 (Rank), split 风格
     * 含义：查询值 v 在树中的排名
     * 注意:v-1 的依赖 T 的类型,如果是浮点数,可能会有精度问题
     */
    int rank_with_split(T v) {
        int x,y;
        split(root,v-1,x,y);
        int ans = tr[x].size + 1;
        root = merge(x,y);
        return ans;
    }
    /**
     * 查询排名 (Rank), bst风格,比split风格快
     * 含义：查询值 v 在树中的排名
     * 注意:v-1 的依赖 T 的类型,如果是浮点数,可能会有精度问题
     */
    T rank(int v) const {
        // 传统的 BST 查询方式, 不依赖 split/merge
        int u = root;
        T ans = 0; // 记录比 v 小的节点数量
        while(u) {
            if( tr[u].val < v) {
                // 当前节点比 v 小, 左子树所有节点也都比 v 小
                ans += tr[tr[u].l].size + 1;
                u = tr[u].r; // 去右子树继续找
            }
            else { // tr[u].val >= v
                // 当前节点不小于 v, 答案在左子树
                u = tr[u].l;
            }
        }
        return ans + 1; // 排名是 "比我小的个数 + 1"
    }


    /**
     * 查询第 k 小 (Kth),bst 风格
     * 含义：查询树中第 k 小的值
     */
    T kth(int k) const {
        int u = root;
        while( true ) {
            int l_size = tr[tr[u].l].size;
            if( k <= l_size ) u = tr[u].l;
            else if( k == l_size + 1 ) return tr[u].val;
            else k -= l_size + 1,u = tr[u].r;
        }
    }

    /**
     * 查询前驱 (Predecessor)
     * 含义：查询值 v 在树中的前驱 (小于v的最大值)
     */
    T pre(T v) {
        // T ans = -2147483647; // 假设为 int 类型的最小值, 表示未找到
        T ans = std::numeric_limits<T>::min(); // 更通用的写法
        int u = root;
        while (u) {
            if (tr[u].val < v) {
                // 当前节点是 v 的一个潜在前驱, 记录下来
                ans = tr[u].val;
                // 尝试在右子树中寻找更大的前驱
                u = tr[u].r;
            } else {
                // 当前节点值 >= v, 前驱一定在左子树
                u = tr[u].l;
            }
        }
        return ans;
    }
    
    /**
     * 查询后继 (Successor)
     * 含义：查询值 v 在树中的后继 (大于v的最小值)
     */
    T succ(T v) {
        int u = root;
        // T ans = 2147483647; // 假设为 int 类型的最大值, 表示未找到
        T ans = std::numeric_limits<T>::max(); // 更通用的写法
        while (u) {
            if (tr[u].val > v) {
                // 当前节点是 v 的一个潜在后继, 记录下来
                ans = tr[u].val;
                // 尝试在左子树中寻找更小的后继
                u = tr[u].l;
            } else {
                // 当前节点值 <= v, 后继一定在右子树
                u = tr[u].r;
            }
        }
        return ans;
    }

     // --- 4. STL 风格查询接口 ---

    /**
     * lower_bound: 寻找第一个 >= v 的值
     * 返回值: 找到的值，如果没找到返回 INF_MAX
     */
    T lower_bound(T v) {
        return succ(v-1); // 等价于 succ(v-1)
    }

    /**
     * upper_bound: 寻找第一个 > v 的值 (等同于 succ)
     * 返回值: 找到的值，如果没找到返回 INF_MAX
     */
    T upper_bound(T v) {
        return succ(v);
    }

    // 打印这个tree, 用于调试
    void print() {
        printf("==== FHQ Tree Print Start (root: %d) ====\n", root);
        print_recursive(root, 0);
        printf("==== FHQ Tree Print End ====\n");
    }
    void print_recursive(int u, int depth) {
        if (!u) {
            return;
        }
        print_recursive(tr[u].r, depth + 1);
        for (int i = 0; i < depth; ++i) {
            printf("    ");
        }
        printf("id=%d, val=%lld, size=%d, fix=%u (l:%d, r:%d)\n",
               u, (long long)tr[u].val, tr[u].size, tr[u].fix, tr[u].l, tr[u].r);
        print_recursive(tr[u].l, depth + 1);
    }
}; // ==== fhq end ===

测试用例

以普通平衡树操作为例：

insert 5
insert 3
insert 7
rank 5       -> 2
kth 2        -> 5
pre 5        -> 3
succ 5       -> 7
delete 5

这组操作可以用模板中的 insert、del、rank、kth、pre、succ 直接组合完成。

应用分类详解

FHQ Treap 的本质是：把动态有序结构拆成可拼接的两半。它适合“集合动态排名”和“序列区间重排”两大模型。

一、动态有序集合

典型模式： 插入、删除、排名、第 $k$ 小、前驱、后继混合出现。

识别信号： 题面要求维护一个会变化的集合，并不断询问大小顺序。

核心建模： 按值分裂。中序遍历就是值从小到大。

应用场景	经典题目	核心思路
普通平衡树	luogu-P3369	六个基本操作
批量删除低于阈值的值	luogu-P1486	全局偏移 + split 后丢弃一边

二、序列区间操作

典型模式： 维护一个序列，支持区间翻转、移动、循环移位。

识别信号： 出现“把 [l,r] 这一段拿出来”“翻转区间”“移动到前面/后面”。

核心建模： 改成按排名分裂。中序遍历不再表示值有序，而表示序列顺序。

应用场景	经典题目	核心思路
区间翻转	luogu-P3391	按排名切出 `[l,r]` 后打翻转标记
区间移动	Codeforces 863D	切出区间后改变 merge 顺序

三、可持久化与离线拼接

典型模式： 需要保留历史版本，或离线维护多个可合并集合。

识别信号： 出现“版本”“复制后修改”“多个集合合并拆分”。

核心建模： split/merge 是天然的结构重组接口，必要时可以改成复制节点的持久化写法。

经典例题

1. luogu-P3369

普通平衡树模板题。适合练习按值分裂的 FHQ Treap。

2. luogu-P1486

郁闷的出纳员。全体工资加减用全局变量维护，低于阈值的员工用 split 批量删除。

3. luogu-P3391

文艺平衡树。把 FHQ Treap 从“按值维护集合”切换到“按排名维护序列”，是掌握区间操作的关键题。

参考

旧草稿：book/pages/data_structure/fhq-treap/草稿.md
例题草稿：book/pages/data_structure/fhq-treap/草稿-例题.md