ODT题解 | 多树二分学习笔记

zhangshirui · 2026-03-11 16:22:04 · 算法·理论

听了冬令营讲课后才知道 P5314 的单 \log 做法，可是看都没人讲，于是决定提一下。文中做法参考自冬令营讲义，同时包含一部分是我的理解和一些 deepseek 的证明，如果存在问题欢迎指出。

前置知识

树剖，这个不用说了，这题的其他题解讲的很细了，平衡树也不用说了，直接讲多树二分。

首先，给定 m 棵重量平衡树 T_{1\sim m}，定义 |T_i| 为第 i 棵平衡树的点数，设 S=\sum_{i=1}^m|T_i|。

这里只考虑二分的一步，并以第 k 小举例。

因为 k>\frac{1}{2}S 的情况和 k\le\frac{1}{2}S 的情况本质相同，把下面内容反过来即可，所以只讨论 k\le\frac{1}{2}S 的情况。

因此我们需要求出删除后一部分元素，并且保证不删除前一半元素的任意方案。

令 a=0.69,b=0.74。（这个是冬令营讲义给的常数，我并不能理解为什么，欢迎补充）

对于一棵平衡树，找到任意一个排名的比例在 [a,b] 的元素 k_i，因为是重量平衡树，所以复杂度是 O(\log\frac{1}{b-a})=O(1) 的。

感性理解一下，重量平衡树的两边儿子总是在一定比例，那你查询一个比例范围时肯定每次缩小一个比例范围的，那子树的值域缩小到这个比例里面，也就差不多是每次折一半，完全被包含的次数，可以参考线段树或者 WBLT。

::::info[deepseek 给的证明]

定理

对于一颗重量平衡树，如果 a 和 b 是固定常数（0 ≤ a < b ≤ 1），则查找排名比例在区间 [a,b] 内的任意一个节点的时间复杂度为 O(1)。

证明

1. 关键性质

重量平衡树满足：对于任意节点，其左右子树的大小比例有常数上界。

设平衡因子为 α（0 < α < 1），则对于任意节点：

• size(left) ≥ α·size(node) 且 size(right) ≥ α·size(node)
• 或等价地，size(left) ≤ (1-α)·size(node) 且 size(right) ≤ (1-α)·size(node)

2. 核心引理

引理1：从根节点到任意比例区间 [a,b] 的路径长度 ≤ C，其中 C 是只依赖于 a、b 和 α 的常数。

证明： 设根节点的比例 p_root = rank(root)/n，其中 n 是总节点数。

考虑路径上的节点序列 v₀=root, v₁, v₂, ..., v_k。每个节点 v_i 的比例 p_i 满足：

• 如果 p_i < a，则下一步走向右子树
• 如果 p_i > b，则下一步走向左子树

关键观察：每次移动，节点的比例会向区间 [a,b] 靠近至少一个常数因子。

更精确地说，设当前节点 v 的比例为 p，其子节点 v' 的比例 p' 满足：

• 如果 p < a（走向右子树），则 p' ≥ p + α·(1-p)
• 如果 p > b（走向左子树），则 p' ≤ p - α·p

这是因为：

• 当 p < a 时，p' = (左子树大小 + 1 + 右子树中更小的部分)/n，至少是 p + α·(n-p)/n ≈ p + α·(1-p)
• 当 p > b 时，对称可得 p' ≤ p - α·p

定义距离函数： d(p) = min(|p-a|, |p-b|)，即 p 到区间 [a,b] 的距离。

可以证明：经过一次移动，d(p) 至少减少为原来的 (1-α) 倍。

因此，从根节点出发，最多需要移动次数： k ≤ log_{1/(1-α)}(1/d(p_root)) + 1

由于 d(p_root) ≤ 1，且 a 和 b 是常数，所以： d(p_root) ≥ min(a, 1-b)（最坏情况根在端点）

但更精确地，最坏情况是根的比例离区间最远，即 p_root = 0 或 1。此时： d(p_root) = min(a, 1-b) 或 min(1-b, a)

所以： k ≤ log_{1/(1-α)}(1/min(a, 1-b)) + 1

由于 a 和 b 是常数，min(a, 1-b) 是正常数，因此 k 是常数。

3. 算法描述

算法 FindAny(root, a, b)：

1. 初始化 node = root
2. 当 node ≠ null：
   • 计算 node 的比例 p = (size(left) + 1) / total_size
   • 如果 a ≤ p ≤ b，返回 node
   • 如果 p < a，node = node.right
   • 如果 p > b，node = node.left
3. 返回 null（区间内无节点）

4. 时间复杂度分析

• 每次迭代：计算比例 O(1)，比较 O(1)，移动指针 O(1)
• 迭代次数：由引理1，最多 C 次，C 是常数
• 总时间复杂度：O(C) = O(1)

5. 常数上界的确定

更精确的常数上界：

设 δ = min(a, 1-b, b-a)/2，表示区间到端点的最小距离。 从最远点（比例 0 或 1）出发，每次移动至少将距离减为原来的 (1-α) 倍。

需要移动的次数满足： (1-α)^k · 1 ≤ δ

解得： k ≥ log_{1/(1-α)}(1/δ)

因此： kmax = ⌈log{1/(1-α)}(1/δ)⌉

当 a=0.3, b=0.4, α=0.3 时： δ = min(0.3, 0.6, 0.1)/2 = 0.05 kmax = ⌈log{1/0.7}(20)⌉ ≈ ⌈log₁.₄₂₈₆(20)⌉ ≈ ⌈8.5⌉ = 9

所以最多 9 步就能找到，与 n=10⁶ 或 n=10⁹ 无关。

6. 结论

对于固定的 a 和 b，算法 FindAny 的时间复杂度是 O(1)，与树的大小 n 无关。∎ ::::

然后，我们要重排树的顺序并找到一个 p\in [1,m]，这个 p 首先要满足：

然后，我们不难发现此时在 p 及之后的所有树的 k 和比 k 大的数都大于等于 k_p，可以全部拉出去毙了，所以我们只需要保证剩下的小于等于 k_p 的数至少有一半就可以了。

如何保证？因为每棵树 T_i 至少有 a|T_i| 个小于等于 k_i 的，而在 i\le p 的树中，那条件可以变成至少有 a|T_i| 个小于等于 k_p 的，那让这个至少的值大于等于 \frac{1}{2}S 即可，列出式子：

移项得到：

那为了保证复杂度，显然不能让被 p 分开的两坨东西差太多，然后就有：

这个限制。汇总一下：

• k_1,...,k_{p-1}\le k_p\le k_{p+1},...,k_m
• \sum_{i=1}^p|T_i|\ge \frac{1}{2a}S
• \sum_{i=p}^m|T_i|\ge (1-\frac{1}{2a})S

考虑如何 O(m) 的找到 p，我们可以通过一个类似快排的方法来找，每次随机选 p，判断往左往右递归是简单的，虽然有 \log 层，但是期望下每层规模减半，复杂度正确。

然后对于所有 p\le i 的树，删除 T_i 中在 k_i 之后的元素，复杂度为 T_i 的深度，所以和查找的复杂度相同为 O(1)。

到这里，我们通过 O(m) 的代价删除了一定比例的元素，复杂度为 O(m\log n)，看着并不优秀，但是我们可以把删空的平衡树扔掉，复杂度就是 \sum_{i=1}^m \log|T_i|，虽然最坏没变，但是其实要优秀不少。

最后分析一下删除的比例，我们留下了 (1-\frac{1}{2a})S 的元素在 k 之后，而每棵树最坏只有 (1-b)|T_i| 的元素被删掉，所以我们至少删掉了 (1-\frac{1}{2a})(1-b)S 个元素，在上面的 a,b 的值下占的比例约为 0.072，于是我们得到了一个 \sum_{i=1}^m \log_{1.077}|T_i| 的做法，在 n=10^6 时只要二分 186 层！而且常数还不小。