平衡树中的 split 和 merge 操作有什么用？

简化版

split 是把一棵平衡树按 key 或排名拆成两棵树，merge 是把两棵有序且互不交叉的树合并成一棵。它们常用于 Treap、Splay 等结构，实现区间删除、区间翻转、排名查询、动态序列维护等操作。前提是拆分和合并后仍要保持 BST 顺序和平衡信息。

详细版

按 key split 时，通常把树拆成 <= x 和 > x 两部分；按排名 split 时，把前 k 个元素拆成一棵树，剩余元素拆成另一棵树。merge 的前提是左树所有 key 都小于右树所有 key，然后根据平衡树规则把两棵树接起来，例如 Treap 按 priority 决定谁做根。

split/merge 的价值在于把复杂区间操作转化成几次树操作。例如删除区间 [L, R]，可以先 split 出 < L 和 >= L，再从后者 split 出 <= R 和 > R，丢掉中间树，再 merge 两边。只要底层结构高度 O(log n)，这些操作通常也是 O(log n) 期望或摊还复杂度。

完整版教学

一、为什么平衡树需要 split 和 merge

普通 BST 的接口通常是 search、insert、delete。但在很多面试和竞赛风格题里，需要维护一个动态有序集合或动态序列，例如“删除排名 10 到 20 的元素”“把区间翻转”“按 key 切开后批量移动”。如果只用单点删除，会把区间操作做成 O(k log n)。split 和 merge 让整段区间能作为一棵子树被整体拿出来。

目标：删除 [L, R]
不使用 split/merge:
  删除 L, L+1, ..., R 逐个处理

使用 split/merge:
  拆出左边、中间、右边
  丢掉中间
  合并左边和右边

这就是 split/merge 的意义：它把“多个元素的操作”提升成“几棵树的操作”。

二、按 key split 的语义

按 key split 通常定义为：给定树 root 和边界 x，把树拆成 A、B 两棵，A 中所有 key <= x，B 中所有 key > x。拆分过程中必须保持每棵树内部仍是合法 BST。

原序列: [1, 3, 5, 7, 9]
split by x=5
A = [1, 3, 5]
B = [7, 9]

在 Treap 中，split 可以递归写：如果 root.key <= x，root 应该属于左树，那么递归拆 root.right；如果 root.key > x，root 应该属于右树，那么递归拆 root.left。递归返回后重新接孩子并更新 size。

三、按排名 split 的语义

按排名 split 更适合动态序列。它把前 k 个元素拆成 A，剩下的拆成 B。这里不一定依赖 key 的数值大小，而是依赖每个节点维护的 size。

操作	输入	输出
`splitByRank(root, 3)`	`[10,20,30,40,50]`	A=`[10,20,30]`, B=`[40,50]`
`splitByRank(root, 0)`	`[10,20]`	A=`[]`, B=`[10,20]`
`splitByRank(root, 5)`	`[1,2,3,4,5]`	A=`[1,2,3,4,5]`, B=`[]`

按排名拆分的关键还是左子树大小。如果左子树大小已经大于等于 k，就继续在左边拆；否则当前节点和左子树都属于前 k 个的一部分，要去右边拆剩余数量。

四、merge 的前提和实现直觉

merge 不是随便把两棵树接起来。它要求左树所有 key 都小于右树所有 key，否则 BST 顺序会被破坏。满足这个前提后，Treap 可以按 priority 决定根：谁 priority 更高，谁做合并后根，再递归合并另一边。

Node merge(Node a, Node b) {
    if (a == null) return b;
    if (b == null) return a;
    if (a.priority < b.priority) {
        a.right = merge(a.right, b);
        pull(a);
        return a;
    } else {
        b.left = merge(a, b.left);
        pull(b);
        return b;
    }
}

这里用小根堆 priority。pull 表示重新计算 size、sum 等增强信息。忘记 pull 会导致后续排名、区间和全部错。

五、区间操作如何拆成三段

假设要删除有序集合中 key 位于 [L, R] 的节点。可以做两次 split：

(A, B) = split(root, L - 1)
(C, D) = split(B, R)

A: key < L
C: L <= key <= R
D: key > R

删除区间 = merge(A, D)

如果是按排名删除第 3 到第 5 个元素，也一样：

(A, B) = splitByRank(root, 2)
(C, D) = splitByRank(B, 3)
root = merge(A, D)

第二次拆 B 时用长度 3，是因为第 3 到第 5 个一共有 3 个元素。这个数字例子能帮助避免排名区间的 off-by-one 错误。

六、常见误区与追问

记忆钩子：区间操作先切三段，中间处理完，再把两边接回去。

误区：merge 可以合并任意两棵 BST。 必须保证左树所有 key 小于右树所有 key，否则合并后不再是 BST。
误区：split 后不需要更新 size。 拆分会改变孩子指针，所有受影响节点的 size、sum、lazy 标记都要维护。
误区：按 key split 和按排名 split 是一回事。 前者按值域切，后者按中序位置切，依赖的信息不同。
追问：split/merge 常在哪些树里用？ Treap 和 Splay 很常见，尤其是 FHQ Treap、文艺平衡树这类动态序列题。
追问：复杂度是多少？ 取决于底层树高，Treap 通常是期望 O(log n)，Splay 通常是摊还 O(log n)。
追问：如何支持区间翻转？ 拆出中间树后打 lazy reverse 标记，再 merge 回去，期间 pushdown 维护懒标记。

七、加强记忆

split 和 merge 是平衡树处理区间问题的基础拼装件。split 把一棵树按 key 或排名拆开，merge 在左右 key 范围不交叉的前提下重新接起来。删除、翻转、区间统计都可以拆成“左段、中段、右段”三棵树，中段处理完再合并。回答这题时要特别强调两个红线细节：merge 必须满足有序前提，split/merge 后必须更新 size、sum 或 lazy 标记，否则结构看似连上了，增强信息已经坏了。

简化版

详细版