笛卡尔树与平衡树：让二叉搜索树 永不退化

① 结构：5 是根；左子树以 3 为根（左 2、右 4）；右子树以 8 为根（左 7、右 9）。

完整描述：5(3(2,4), 8(7,9))。

② 树高 = 3（从根 5 到叶子 2 经过 3 条边）。n = 7 时理论上最小高度是 ⌈log₂8⌉ = 3，所以这棵树恰好是最优形态。

③ 中序遍历：2, 3, 4, 5, 7, 8, 9——恰好递增，验证了 BST 的性质。（注意原数据里没有 6，如果插入的是 1..7 就是 1..7 递增。）

④ 插入 1..7 时的形态：1 是根，2 是 1 的右孩子，3 是 2 的右孩子……一条向右的链，树高 = 7 = n。

对比：同样 7 个元素，一个有规律（5,3,8,2,4,7,9 呈"中间数先插"的规律）树高 3；一个递增，树高 7。查找最后一个元素的比较次数分别是 3 次和 7 次。

本题的训练目标：亲手体会"树高完全由插入顺序决定，而与元素个数无关"。这也解释了为什么"先取中间的数"建树能得到最平衡的形态——这正是"二分建树"的原理。

推论：如果一个 BST 能被真正随机化地插入，期望树高是 O(log n)。这直接引出了 Treap 的设计思路。

初始结构：x 有两个孩子，左孩子是 y，右孩子是 w；y 没有左孩子，右孩子是 z。

用嵌套写法：x(y(_, z), w)。

旋转过程（对 x 右旋）：

① x 的左孩子是 y，y 的内子树（右子树）是 z；

② 把 z 过继给 x 当左孩子：lc[x] = z；

③ x 降级为 y 的右孩子：rc[y] = x；

④ y 替代 x 原来的位置。若 x 原是整棵树的根，则新根是 y。

旋转后结构：y(_, x(z, w))。

中序验证：

· 旋转前中序：y、z、x、w（先左 y，再 y 的右 z，再 x，再右 w）

· 旋转后中序：y、z、x、w（先左子树空，再 y，再 y 的右子树 x（其中 x 的左 z、右 w））

完全一致！这正是旋转的定义要求。

高度变化分析：

· 旋转前：因 z 挂在 x 的左子树的下面，x 的左高度为 2，右高度为 1。

· 旋转后：x 的左右高度都是 1；y 的右高度是 2，左为 0。

但注意：这次旋转并没有让整棵树变得更平衡（y 反而歪向了右边）！它只是把"左边过深"的具体形状改了。所以"旋转一定让树更平衡"是错的——只有针对正确的失衡类型选择正确的旋转，才能修复平衡。这正是为什么 AVL 要分 LL/RR/LR/RL 四种情况讨论。

本题的训练目标：把"旋转只改 3 条边、中序不变"这一点彻底掌握，并意识到"旋转不是万能的，必须用对场合"。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int lc[MAXN], rc[MAXN], key[MAXN], pri[MAXN], sz[MAXN], cnt[MAXN];
int tot = 0, root = 0;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int newNode(int k) {
    key[++tot] = k;  pri[tot] = rng();
    sz[tot] = cnt[tot] = 1;
    lc[tot] = rc[tot] = 0;
    return tot;
}
void pushup(int u) { sz[u] = sz[lc[u]] + sz[rc[u]] + cnt[u]; }

void rotR(int& y) {
    int x = lc[y];
    lc[y] = rc[x];  rc[x] = y;
    pushup(y); pushup(x);              // 自下而上
    y = x;
}
void rotL(int& x) {
    int y = rc[x];
    rc[x] = lc[y];  lc[y] = x;
    pushup(x); pushup(y);
    x = y;
}

void insert(int& u, int k) {
    if (!u) { u = newNode(k); return; }
    if (k == key[u]) { cnt[u]++; pushup(u); return; }
    if (k < key[u]) { insert(lc[u], k); if (pri[lc[u]] < pri[u]) rotR(u); }
    else            { insert(rc[u], k); if (pri[rc[u]] < pri[u]) rotL(u); }
    pushup(u);
}

void inorder(int u) {
    if (!u) return;
    inorder(lc[u]);
    for (int i = 0; i < cnt[u]; i++) cout << key[u] << ' ';
    inorder(rc[u]);
}

int main() {
    int a[5] = {5, 3, 8, 3, 1};   // 故意含重复值，测试 cnt
    for (int x : a) insert(root, x);
    inorder(root);
    cout << '\n';
    cout << "size = " << sz[root] << '\n';
    return 0;
}

预期输出：1 3 3 5 8，然后 size = 5。

自查清单：

· tot 和 root 都初始化为 0 了吗？

· rotR / rotL 的参数是引用（int&）吗？如果不是引用，新根无法传回给调用者。这是最容易被忽略的一点。

· pushup 的顺序是"先下沉的节点、后上位的节点"吗？

· insert 里 pri[child] < pri[u] 的条件对吗？（小根堆，所以是父 pri 必须小于孩子；一旦孩子更小就违反，需要旋转）

· 中序输出时，对 cnt[u] > 1 的节点是否输出了多次？（因为可重集里同一个值出现多次）

调试技巧：写完后可以打印每个节点的 (key, pri, sz) 并检查"每个父的 pri 都小于孩子的 pri"——这是验证 Treap 正确性最快的方法。

① 错误。只有 AVL 是严格 O(log n)。Treap 是期望 O(log n)（单次最坏可为 O(n)），Splay 是均摊 O(log n)（单次最坏可为 O(n)）。三种"平衡"的含义完全不同。

② 错误。AVL 更平衡意味着查询路径更短，所以查询确实可能更快。但 AVL 维护平衡的代价更大——插入删除时要频繁更新高度并可能多次旋转，而 Treap 只需比较一次 pri 决定是否旋转。对于"插入删除多、查询少"的场景，Treap 反而更快。"更平衡"不等于"综合更快"。

③ 错误。笛卡尔树的形态完全由数组决定，不保证平衡。例如数组 [1, 2, 3, 4, 5]（递增），最小值 1 在下标 1，它的右子树包含下标 2..5；在右边这部分里最小值是 2（下标 2），再往右……结果是一条向左的斜链（每次都是"根 + 右子树"，没有左孩子）。反之若数组对应"最小元素恰好在中间"的完全二叉树形态，笛卡尔树也是完全平衡的。

④ 错误。Splay 是均摊 O(log n)——意思是"m 次操作的总时间是 O((n+m) log n)"。单次操作慢，意味着它把"预支"的便宜还回去了。在 OI 比赛（只限制总时间）中，均摊复杂度完全够用。而且 Splay 还有 Treap 做不到的能力：区间操作（翻转、切分、移动）。

⑤ 正确。以最小值笛卡尔树为例，数组递增时 a[1] 最小，成为根；它的左子树为空（因为左边没元素），右子树是 a[2..n]，其中 a[2] 最小……结果是一条只有右孩子的斜链，高度 n。完全对称地，若数组递减，会变成只有左孩子的斜链。

⑤ 的补充说明：这就是为什么笛卡尔树不能用来做动态查找——它的形态由数据决定，可能完全退化。它的用途是"提供一种树形结构来做静态统计"，而不是"加速查找"。

本题的最大价值：它逼你分清"严格 / 期望 / 均摊"这三种复杂度保证，以及"更平衡"和"更高效"之间的区别。这三组概念是平衡树部分最容易被混淆、也最容易出判断题的地方。

插入 10：树中只有 10，BF[10] = 0，平衡。

插入 20：20 > 10 → 10 的右孩子。BF[10] = 0 − 1 = −1，平衡。（|−1| ≤ 1 是允许的）

插入 30：30 > 10、30 > 20 → 20 的右孩子。回溯：hgt 更新后 BF[20] = −1，BF[10] = −2。节点 10 失衡，且方向是"右右"→ RR 型 → 对 10 左旋一次。

旋转后：20 是根，左孩子 10，右孩子 30。三个节点的 BF 全为 0。完全平衡。

插入 40：40 > 20、40 > 30 → 30 的右孩子。回溯：BF[30] = −1，BF[20] = 0 − 2 = −2。20 失衡，RR 型 → 对 20 左旋。

旋转后：30 是根，左孩子 20（左孩子 10），右孩子 40。BF[30] = 1 − 1 = 0，BF[20] = 0，BF[40] = 0。平衡。

插入 25（关键的一步）：25 > 30？不，25 < 30 → 走左；25 > 20 → 走右；挂到 20 的右边。

回溯：hgt[25] = 1，hgt[20] = 2，hgt[30] = 3。BF[30] = hgt[lc] − hgt[rc] = 2 − 1 = +1，暂时安全。继续看更上层——30 是根，所以没有上层了。

慢着，需要重新确认！让我们重新梳理：插入 40 后树是 30(20(10, _), 40)。hgt[20] = 2（因为 20 有左孩子 10），hgt[40] = 1，hgt[30] = 3，BF[30] = 2 − 1 = +1。注意这里 BF 是 +1，不是 0——所以插入 40 后就已经略微左偏了，只是还没超过 1。

现在插入 25：25 挂在 20 的右边。此时 hgt[20] = max(1, 1) + 1 = 2（不变！因为 20 原来就有左孩子 10，高度已经是 2）。所以 20 的高度没有变化，30 的高度也不变。整棵树插入 25 后没有引发任何失衡！

最终形态：30(20(10, 25), 40)。BF[20] = 0，BF[30] = 1，BF[40] = 0，其余叶子 BF = 0。所有 |BF| ≤ 1，合法。

本题的关键教学点：插入不一定引发失衡。只有当"新节点让某条路径的高度真正增加了"时，才可能失衡。如果插入的位置"填进了原来空着的那个位置"（左右由不平衡变成平衡），高度反而不会增加。

建议：把这道题的五步全部手画一遍，并特别留意"高度是否真的变化"。90% 的 AVL 手算错误都源于"以为每次插入都会让高度加一"。

根本区别：线段树的区间划分是"静态的"，Splay 的区间划分是"动态的"。

线段树把 [1, n] 固定二分成一棵树，每个节点永远对应同一个下标区间。一旦元素移动，整个划分就失效了——所以线段树只能"改值"，不能"改序"。

而 Splay 维护的是"中序顺序"，只要通过旋转保持中序不变，元素的相对顺序就可以任意重排。"移动区间"本质上是"改变中序顺序"，Splay 天然支持。

具体做法（"剪切 + 粘贴"三步）：

第一步（剪）：用夹逼技巧把 [l, r] 切出来。
splay(l-1, 0); splay(r+1, l-1);
记 sub = ch[ch[root][1]][0]，这就是区间 [l, r] 对应的子树。把 ch[ch[root][1]][0] = 0，并把 sz 更新——区间就从树上"剪掉"了。

第二步（定位）：在剩下的 n − (r−l+1) 个元素中，找到"新位置 p"对应的两个边界节点。注意因为剪掉了一段，原来的下标要重新映射：若 p < l，则边界节点是原来的 p−1 和 p；若 p > r，则要先减去区间长度。然后把这两个节点 splay 上去。

第三步（贴）：把剪下来的 sub 接到新位置——即挂成"根的右孩子的左子树"（与夹逼的位置一致）。然后沿路径 pushup 更新 sz。

复杂度：三次 splay，均摊 O(log n)。整个操作是 O(log n)——而如果用数组实现"移动区间"，需要 O(n) 次搬移。

同类操作还有：区间删除（剪下来直接丢掉）、区间插入（把新序列建成一棵 Splay 后 merge 进去）、区间赋值 / 区间翻转（打标记）、区间求和（维护 sum）。所有这些"改变顺序"或"整段处理"的操作，Splay 都能 O(log n) 完成。

对比记忆：
· 区间改值（加、乘、赋值、取最值）→ 线段树 / 树状数组（更快更简单）
· 区间改序（翻转、移动、切分、合并）→ Splay / FHQ-Treap（线段树做不到）

典型题目：P2596 [ZJOI2006] 书架（区间的移动 / 置顶 / 置底）、P3850 [TJOI2007] 书架（在位置 p 插入，用 FHQ 更简单）。

① 单调栈过程：

i=1, a=3：栈空，last=0，无父亲、无左孩子。1 暂时是根。栈：[1]

i=2, a=1：栈顶 1 的 a=3 > 1 → 弹出，last=1。栈空停止。栈空 → 2 成为新根；last=1 → lc[2]=1。栈：[2]

i=3, a=4：栈顶 2 的 a=1 < 4 → 不弹。栈非空 → rc[2]=3，3 是 2 的右孩子。栈：[2,3]

i=4, a=5：栈顶 3 的 a=4 < 5 → 不弹。→ rc[3]=4。栈：[2,3,4]

i=5, a=2：栈顶 4 的 a=5 > 2 → 弹出，last=4；栈顶 3 的 a=4 > 2 → 弹出，last=3；栈顶 2 的 a=1 < 2 → 停。栈非空 → rc[2]=5；last=3 → lc[5]=3。栈：[2,5]

最终树结构：根 = 2；lc[2]=1，rc[2]=5；lc[5]=3；rc[3]=4。

即 2(1, 5(3(_, 4), _))，与图 2 完全一致 ✅

② 求区间 [3, 5] 的最小值：

在树上找下标 3 和下标 5 的 LCA。下标 3 的祖先链是 3 → 5 → 2 → （根）；下标 5 的祖先链是 5 → 2 → （根）。公共祖先中深度最大的是下标 5。

所以 LCA(3, 5) = 5，对应值 a[5] = 2。答案：区间 [3, 5] 的最小值是 2。

暴力验证：a[3]=4, a[4]=5, a[5]=2 → min = 2 ✅

关键检查：LCA 的下标必须在 [l, r] 内。这里 LCA 是 5，确实在 [3, 5] 中，符合理论。

⚠️ 一个必须注意的方向问题：如果你要求的是最大值的区间查询，就必须建大根堆笛卡尔树（根是最大值）。最小值笛卡尔树只能回答"区间最小值"，反过来用会得到错误答案。

本题的训练目标：把"单调栈建树"和"LCA 求 RMQ"两条线串起来。实际做题时，如果要多次查询区间最值，通常会转成"欧拉序 + ST 表"或直接用 ST 表——但理解笛卡尔树与 LCA 的对应关系，是很多高级题目的关键一步。

方案一：平衡树（Treap）。最直接的方案。

· 插入/删除 O(log n)，查存在 O(log n)，第 k 小 O(log n)。

· 代码量约 100 行。支持在线操作（来了就做）。

· 缺点：常数较大，容易写错。

方案二：离散化 + 树状数组 + 倍增求第 k 小。

· 先读入所有操作的数值，离散化成 1..m 的排名（因为要"第 k 小"，值域必须可比）。

· 用树状数组维护每个值的出现次数：插入 = 单点 +1，删除 = 单点 −1，查存在 = 单点查询。

· 第 k 小用树状数组上的倍增：从高位往低位试，累加 c[i] < k 时的部分，最终定位到第 k 小对应的值。O(log m)。

· 代码量约 60 行，比平衡树短得多，常数小 3~5 倍。

· 缺点：必须离线（要先知道所有可能出现过的数值）。如果题目强制在线（每次操作的参数依赖上一次的答案），这个方案就不能用。

方案三：值域线段树 / 权值线段树 + 动态开点。

· 在值域上建线段树，每个节点记录"这个值域区间里有多少个数"。

· 插入/删除 = 单点更新 O(log V)；第 k 小 = 从根往下比较左子树的 count 与 k，O(log V)。

· 如果值域很大（如 10⁹），用动态开点或离散化。用动态开点时不需要离线。

· 代码量约 80 行，常数比平衡树小。而且很容易改造成可持久化（主席树）——这是它相比方案二的巨大优势。

三种方案的对比表：

选择建议：

· 能离线 → 首选离散化 + BIT，短、快、稳。

· 要在线但值域不大 → 权值线段树，常数小。

· 要在线且要区间操作（翻转/切分） → Treap / Splay。

· 要可持久化 → 权值线段树（主席树）或 FHQ-Treap。

本题的最大价值：同一个需求有三条路，各有取舍。高手的标志不是"会写平衡树"，而是"知道什么时候不该写平衡树"。在 90% 的题目里，离散化 + BIT 都是最快的解法。

证明思路（关键是把 Treap 转化成"随机 BST"）：

第一步：等价转化。把 n 个 key 按 pri 从小到大排序，得到序列 kπ(1), kπ(2), …, kπ(n)。按这个顺序依次插入一棵普通 BST，得到的树恰好就是这棵 Treap。（因为 pri 最小的一定成为根，而它在插入序列中排第一；其余元素递归地按同样方式分配。）

由于 pri 是独立均匀随机的，"按 pri 排序"等价于"随机打乱"。所以 Treap = 随机打乱顺序后建的 BST。

第二步：分析随机 BST 的高度。对任意一对 key u < v，u 是 v 的祖先当且仅当 u 是 {u 到 v 之间所有 key} 中 pri 最小的那个。

理由是：Treap 中，一个节点 x 的子树包含"键值在某个连续区间内"的所有节点（BST 性质）；而 x 是这棵子树的根当且仅当 x 的 pri 是这个区间内最小的（堆性质）。

第三步：计算深度。节点 v 的深度 = 它的祖先个数 = 满足"u 是 v 的祖先"的 u 的个数 = Σ_u≠v [u 是 [min(u,v), max(u,v)] 内 pri 最小的]。

对固定的 u、v（假设 u < v），区间 [u, v] 内共有 v − u + 1 个 key。由于 pri 是独立的随机值，每个 key 成为"区间内最小 pri"的概率都是相等的，即 1/(v − u + 1)。

所以： E[depth(v)] = Σ_u<v 1/(v−u+1) + Σ_u>v 1/(u−v+1) ≈ 2 ln n = O(log n)

（第一个和式是 1/2 + 1/3 + … + 1/v ≈ ln v，第二个和式同理，都是调和级数。）

第四步：树高。任一节点的期望深度都是 O(log n)，所以期望树高 = O(log n)。更严格的结论（用 Chernoff 界）可以证明"树高超过 c·log n 的概率是指数级小的"。

本题的收获：① "随机化 = 等价于随机顺序"这个转化思想极其重要，它把"数据结构问题"变成了"概率统计问题"；② 调和级数 Σ1/i ≈ ln n 是随机 BST、快排、跳表分析的共同工具；③ 注意这里算的是 期望深度，单次最坏仍然可能是 O(n)——但概率极小。

延伸：同样的分析方法可以证明"随机快排的期望复杂度是 O(n log n)"（pivot 的排名是随机的，每次划分期望把问题规模减半）。另一个深刻的对照：log2 n 与 ln n 差一个常数倍（约 1.44），所以随机 BST 比完全平衡树高大约 1.44 倍——这就是 Treap 的"平衡代价"。这个 1.44 恰好也是 AVL 树高度上界里的系数，不是巧合。

普通 Treap 不能的原因：它的 BST 键是"值"，不是"位置"。

普通 Treap 按键值建树，中序是"按值排序"。要做区间翻转，必须能"定位到第 l 个和第 r 个元素"——但 Treap 里"第 k 小"是按值排的，而不是按原序列的位置排的。翻转一个"值域区间"没有意义。

更根本的是：一旦旋转，"第 k 个位置"对应的节点就变了。而按值建的 Treap 没有"位置"这个概念。

改造方案一（按位置建树的 Treap）：让 BST 的键变成"原序列的下标"，而不是值。这样中序就是原序列顺序。此时：

· "第 k 个元素"用 sz 定位，和 Splay 的 kth 一样。

· "区间 [l, r]"需要"切出中间那段"——Treap 没有切片能力，但不妨碍用 split 按位置切开。这就引出了方案二。

改造方案二（FHQ-Treap，推荐）：用 split(u, k, x, y) 把树按"前 k 个元素"拆成两棵，用 merge 合并。那么区间翻转变成：

split(root, l-1, a, b);
split(b, r-l+1, b, c);
rev[b] ^= 1;　　　// b 就是区间 [l,r]
root = merge(a, merge(b, c));

四行搞定，比 Splay 的夹逼还简单！而且 split / merge 都不用旋转，pushdown 的处理也更直观。

为什么 FHQ-Treap 能按位置切分？因为 split(u, k, a, b) 的语义是"把以 u 为根的树拆成"前 k 个元素"和"其余"两棵"。它通过递归地比较 sz[lc[u]] + 1 与 k 来决定怎么切，完全不依赖键值的大小关系——所以既支持按值切，也支持按位置切。

三种做法的对比：

结论与建议：现在（以及过去十年）竞赛圈的主流是 FHQ-Treap。它用同一套 split/merge 模板，同时解决了"普通平衡树"和"区间平衡树"两类问题，还能可持久化。Splay 主要的价值在于理解"伸展"这一巧妙的自调整思想，以及在某些需要"把某节点提到根"的场景（如 LCT）中不可替代。

延伸：把 Treap 的键改成"位置"后，其实就已经不是"查找结构"而是"序列结构"了。这正是平衡树的两大用途分野：一类维护"值的集合"（查前驱后继），一类维护"序列"（区间操作）。看清这一点，你就能在拿到题目时立刻判断该用哪一种。

① 对称性来自"取负"这一操作。

观察：min(a[l..r]) = −max(−a[l..r])。也就是说，"求最小值之和"可以转化为"对数组取负后求最大值之和，再取负"。

所以两道题在算法上完全镜像，唯一的区别是：最小值用"小根堆笛卡尔树"，最大值用"大根堆笛卡尔树"（或者说，建树的时候把比较符号 > 改成 <）。

统一公式：答案 = Σ_u a[u] × (szL[u] + 1) × (szR[u] + 1)，其中 szL, szR 是以 u 为根的子树中左右孩子的大小。

也可以完全不用笛卡尔树：用单调栈分别求出每个 i 的"左边第一个比它大/小的位置"和"右边第一个比它大/小的位置"，直接套 (i − L[i]) × (R[i] − i)。这其实就是笛卡尔树的"隐式形态"——不需要真的把树建出来。

结论："最值之和"这类题的核心是"贡献法 + 单调栈"，笛卡尔树只是给它一个更直观的树形解释。两道题看起来对称，是因为"最小"与"最大"在数学上通过取负完全等价。

② 次小值之和：难度陡增。

为什么难？因为"最小值"有唯一定位（一个区间的最小值位置唯一，可以精确地归功到某个元素上），而"次小值"没有这种"唯一归属"的简单结构——它依赖于"最小值在哪里"。

可行思路一（笛卡尔树 + 分类讨论）：在笛卡尔树上考虑每个节点 u 作为"次小值"的区间。设 u 的父节点是 p（p 的值比 u 小）。对某个包含 u 的区间来说，u 是次小值当且仅当区间包含 u、不包含比 u 更小的其他元素、但包含至少一个比 u 小的元素（即包含 p 或 p 的某个祖先）。

于是需要对每个 u 分别计算"包含 u、且最小值恰好是 p（或 p 的某祖先）"的区间数。这需要在笛卡尔树上做更复杂的统计（通常配合"每个节点的子树区间边界"和"父链"信息）。

可行思路二（分治 + 单调栈）：用"最小值分治"——每次以区间最小值为分界把区间劈开，然后把"跨过最小值位置"的区间单独统计（这些区间的次小值就是左右两侧各自的最小值中的较小者）。这需要用"启发式合并 + 数据结构"或"笛卡尔树上的树形 DP"来加速。

可行思路三（排序 + 并查集）：把元素从小到大依次"激活"，用并查集维护"激活元素形成的连续段"。当第 t 个元素被激活时，它把相邻的段合并——此时可以统计"以它为第 t 小（即次小、第三小……）的那些区间"。这个技巧叫做"按值排序 + 并查集合并"，是处理"第 k 小之和"类问题的通用套路。

复杂度：思路三可以做到 O(n log n)（排序 + 并查集），是最实用的做法。

本题的价值：它展示了一个重要的规律——"最小值/最大值"问题有唯一的结构化归属（笛卡尔树），而"次小值/第 k 小值"问题往往需要"排序 + 并查集"这种"增量式"的处理方式。从"静态结构"转向"增量处理"，是算法思维的一次重要升级。

延伸练习：P4755 Beautiful Pair 就是这类问题的经典代表；"直方图中最大矩形"（P4147）则是最小值笛卡尔树的标准应用。

能提供"最坏情况 O(log n)"的结构：

① AVL 树。因为 |BF| ≤ 1 是硬约束，任何时刻树高都不超过 1.44 log₂(n+2)。所以单次插入/删除/查找严格 O(log n)。这是最直接的答案。

② 红黑树。虽然没有 AVL 严格，但同样是硬约束（最长路径 ≤ 2 × 最短路径），所以树高 ≤ 2 log₂(n+1)，严格 O(log n)。

③ 替罪羊树。虽然插入时可能临时不平衡，但一旦"某棵子树的大小超过 α 倍"，就立即重建。可以证明重建的代价被"均摊"到之前的插入上，但更关键的是：树高始终被约束在 O(log n) 以内（因为不平衡的节点会被立即重建）。所以每次操作的最坏代价是 O(log n)（重建的代价由之前的操作"预支"了）。严格说替罪羊树是"均摊 O(log n)"，但它的树高确实始终有界。

④ B 树 / 2-3-4 树。多路平衡树，通过"节点分裂/合并"保持所有叶子在同一深度，树高严格为 O(log n)。红黑树本质上就是 2-3-4 树的二叉化表示。

为什么 Treap 做不到？

因为 Treap 的 pri 是随机生成的。虽然 pri 恰好单调递增（导致链式退化）的概率是 1/n!（指数级小），但这个概率不是零。所以在最坏情况下，Treap 的树高可以是 n，单次操作可以是 O(n)。

要让 Treap 变成最坏 O(log n)，需要给 pri 加上"强制约束"——比如"如果某个节点的深度超过阈值就重建"（这就是替罪羊树的思想），或者"用确定性的优先级使得堆性质与平衡性同时成立"（但这样的优先级很难构造）。本质上，随机化的代价就是"放弃最坏情况保证"。

为什么 Splay 做不到？

Splay 的自调整策略只看"访问频率"，不看"树的高度"。可以构造出这样的操作序列：先访问一个"两边都不平衡"的节点把它提到根，此时树变得很歪；然后再访问最深的节点，这次操作就是 O(n)。

关键点在于：Splay 的单次操作代价可以很高，但它"改善"了后续操作的代价。均摊分析表明"总的改善量"足以补偿"总的高代价"。但如果只看单次，Splay 就是 O(n) 的。这是"均摊"与"最坏"的本质区别。

三种保证的对比：

竞赛中的实际选择：绝大多数题目只限制"总时间"，所以期望和均摊复杂度完全够用，而且 Treap / Splay 的常数比 AVL 小、代码比红黑树短。只有在"交互题"或"需要保证单次响应时间"的场景下，严格最坏保证才有必要。

本题的核心收获：分清 严格 / 期望 / 均摊 三种复杂度保证的含义与适用场景。这是算法分析中最重要的一组概念之一，也是本讲"思考与启发"部分最想让你带走的东西。