基于替罪羊树维护的 K‑D Tree 复杂度证明

MZMTab · 2026-07-19 09:08:30 · 算法·理论

UPD on Jul 22: fix typo & 添加 U 群相关讨论

摘要

本文证明了替罪羊树维护 K‑D Tree 的查询、重构复杂度，打破算法竞赛社区关于该做法复杂度的错误观点。

This article proves the query and reconstruction complexity of the scapegoat tree maintaining a K‑D Tree, refuting the incorrect belief in the competitive programming community regarding the complexity of this approach.

:::info[U 群关于这个的讨论节选（2026-07-22）]

MZMTab 2026-07-20 17:37:48
vuqa,https://www.luogu.com.cn/article/shh0v8zb

qqwq 2026-07-20 17:43:33
@MZMTab ok

qqwq 2026-07-20 17:43:40
kdt这一段oiwiki是我写的

qqwq 2026-07-20 17:44:21
但是你好像没有提出新东西啊

qqwq 2026-07-20 17:44:31
没有保证，只是不保证是根号的

qqwq 2026-07-20 17:44:37

MZMTab 2026-07-20 17:44:59
好像要这么说也有道理

qqwq 2026-07-20 17:46:40
如果你认为这个有歧义的话，这里确实可以改一下

qqwq 2026-07-20 17:47:53
不过我觉得做了这个工作还是值得认可的也可以把它提交到oiwiki（）

MZMTab 2026-07-20 17:48:10
主要是看网上没人写

gxy 2026-07-20 17:48:24
这个不是常识吗

gxy 2026-07-20 17:48:46
https://www.luogu.com/article/cod5s33o ，远古blog早有记载

gxy 2026-07-20 17:49:25
感觉我学的时候，周边人都知道这是

MZMTab 2026-07-20 17:49:55
emmm

MZMTab 2026-07-20 17:52:17
似乎有点瑕疵，没有 akra-bazzi后面的积分项的分析

qqwq 2026-07-20 17:54:07
就是他觉得，这个没保证，是指可能退化成暴力

:::

前言

很多选手会使用替罪羊树结构来维护．但是注意到在刚才的复杂度分析中，要求儿子的子树大小严格减半，即树高必须为严格的 \log n+O(1)，而替罪羊树只满足树高 O(\log n)，故查询复杂度无法保证． ——OI wiki K‑D Tree

~~我写完后估计就要改了~~。

本文的目的即证明使用替罪羊树维护 K‑D Tree 的复杂度。其中，本文重点分析二维情况。

如果你并不了解这一做法，可以参考 aaron0919 的 P14312 【模板】K-D Tree の题解，但是其中的复杂度证明是错误的，详细原因请参考后文。

本文仅讨论交错建树。对于二维而言，即建树时每层的排序方式即按 x 坐标排序与按 y 坐标排序交替。

前置知识

我们会使用的工具：

均摊分析和替罪羊树的复杂度证明
Akra‑Bazzi 定理，可以参考 GONGGONGJOHN 的从主方法到Akra-Bazzi定理

Akra‑Bazzi 定理

现不加证明地给出 Akra‑Bazzi 定理：

设 f(x) 为非负函数，

T(n)= \begin{cases} \Theta(1) ,1 \le n \le X_0\\ \sum \limits_{i=1}^k a_i \cdot T(b_i n) +f(n) \ ,n \gt X_0 \end{cases}

满足

\forall 1 \le i \le k,a_i \gt 0,0\lt b_i \lt 1, X_0 \gt \frac{1}{1-b_i},f(n)\text{ 满足多项式增长条件}

对于定义在非负实数的函数 f(n)，称 f(x) 满足多项式增长条件当且仅当 \exists c_1,c_2>0,\{b_k\},b_i \in(0,1),\forall x \ge 1,1 \le i \le k,u \in [b_i x,x],c_1 f(x) \le f(u) \le c_2 f(x)。

由定义可知，若存在 c \ge 0，使得 |g^\prime(x)| \in \mathcal{O}(n^c)，则 g(x) 满足多项式增长条件。

特别地，a,b\in \mathbb R，f(n)= \mathcal{O}(n^a\log ^b n)，则 f(n) 满足多项式增长条件。

则

T(n) = \Theta \left (n^p \left (1+\int _1^n \frac{f(x)}{x^{p+1}} dx\right)\right )

其中 p 为方程 \sum \limits _{i=1}^k a_i b_i ^p =1 的实数根。

:::info[为什么和论文 [1] 中的描述不一样]

我本来是想要用论文 [1] 中的版本，但是我看到里面有这样一句话：

g(x)$ is defined for real values $x$, and is bounded, positive and nondecreasing function $\forall x \ge 0

此处的 g(x) 即上文的 f(x)。

注意到其中有一个 bounded，非常奇怪，因为连 g(n)=n 都不满足，这不合理。于是检索发现参考资料 [5] 的问答，接着查阅了参考资料 [4] 中 Leighton 的讲义，认为 bounded 是个 typo。

由于参考资料 [4] 中的描述 "These conditions are somewhat less restrictive than those of [1]"，且为互联网上最常见的描述，所以选择了这种描述。

:::

关于平衡树相关的一些术语

但是 $\alpha$‑高度平衡不能推出 $\alpha$‑重量平衡。举一个反例左子树为深度为 $k$ 的链，大小为 $k$；右子树为深度为 $k$ 的完全二叉树大小为 $2^k-1$，整棵树总结点树为 $2^k+k$。当 $k$ 足够大时，对于任意 $\alpha>0.5$，这颗树可以满足 $\alpha$‑高度平衡；但左右子树差异极大，无法满足 $\alpha$‑重量平衡。 ## 完全平衡时的查询复杂度证明借鉴了 [OI wiki K‑D Tree](https://oi-wiki.org/ds/kdt/#%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90) 的证明。先考虑二维情况。若查询的矩形为 $R$，让我们考虑一个结点代表的矩形 $P$ 有以下三种情况： 1. $R$ 完全包含 $P$； 2. $R$ 和 $P$ 相离； 3. $P$ 完全包含 $R$； 4. $P$ 与 $R$ 相交但互不包含。其中 3 和 4 两种情况是要继续递归的，即复杂度为 3 和 4 两种情况的结点数之和。而第 3 种情况有一个平凡的上限：$\mathcal{O}(h)=\mathcal{O}(\log n)$，$h$ 为树高。重点来考虑第 4 种情况。由于位于第 4 种情况时，一定在矩形的边缘。我们需要统计的总点数一定小于四个条边上的矩形个数和。每个结点会的四个孙子结点将该矩形分为四个子矩形。而一条线段只能通过这其中的两个子矩形，所以可以得到这部分的递归式： $$ T(n)= 2 T(\frac{n}{4}) +\Theta (1) $$ 由主定理解得 $$ T(n) = \Theta(\sqrt n) $$ 这个大于 $\mathcal O(\log n)

类似地分析可以得到 k 维的情况：

T(n)= 2^{k-1}T(\frac{n}{2^k}) + \Theta(1)

由主定理，得到经典结论：

T(n)= \Theta(n ^{\frac{k-1}{k}})

替罪羊树维护的查询复杂度证明（二维情况）

有了上面的基础，我们可以考虑在替罪羊树上有什么不同。

可以发现，唯一的区别就是划分出来的四个子矩形大小不相同。

考虑一种极端情况：所有子树都恰好满足 \alpha‑重量平衡。为了方便我们假设现在讨论的子树大小为 n。那么四个孙子结点的子树的大小分别为：

\alpha ^2 n,\alpha(1-\alpha)n,\alpha(1-\alpha)n,(1-\alpha)^2n

取其中最大的两个，得到递归式：

T(n)=T(\alpha^2n)+T(\alpha(1-\alpha)n)+ \Theta(1)

可以直接套用 Akra‑Bazzi 定理。

我们先讨论一个特殊情况：\alpha=0.6=\frac{3}{5}。

则

\left(\frac{9}{25}\right) ^p + \left( \frac{6}{25}\right)^p=1

这是一个超越方程，没有初等函数通式解。通过二分等方法可以解得

p \approx 0.57

而

\int _1 ^n \frac{1}{x^{p+1}} dx = \left(\frac{x^{-p}}{-p} \right)^n _{1} = \frac{1}{p}\left( 1- n^{-p} \right) \le \frac{1}{p} =\Theta(1)

故总复杂度为

T(n)= \Theta(n^p) \approx \Theta(n^{0.57})

而在 OI 可能的数据范围内（n \le 10^6），n^{0.07} \le 2.63，这个复杂度和 \Theta(\sqrt n) 几乎没有区别。

更一般地，考虑函数

g(x)= \alpha^{2x}+ (\alpha(1-\alpha)) ^x -1

考察参数 \alpha 的取值对零点的影响。

由于 \alpha \in (0.5,1)，g(x) 在 \mathbb R_{+} 单调递减。故函数有唯一零点。

g(0.5)= \alpha + \sqrt {\alpha(1-\alpha)} -1

我们猜想 g(0.5) >0，这等价于

\sqrt {\alpha(1-\alpha)}>1 - \alpha

左右显然都是正的。两边平方，得

\alpha(1-\alpha) >(1-\alpha)^2

同时除以正数 1-\alpha，得

\alpha > 1- \alpha \Leftrightarrow \alpha > 0.5

显然成立。故当 \alpha \in (0,5,1) 时，g(0.5)>0。

而 g(1)=\alpha^2+\alpha(1-\alpha)-1=\alpha-1<0。

故 p \in(0.5,1)。

则

\int _1 ^n \frac{1}{x^{p+1}} dx = \left(\frac{x^{-p}}{-p} \right)^n _{1} = \frac{1}{p}\left( 1- n^{-p} \right) \le \frac{1}{p} =\Theta(1)

故复杂度为

T(n)=\Theta(n^p)

当 \alpha \in(0.5,0.75] 时，p \in (0.5,0.68]。而 (10^5)^{0.18} \le 8，在 OI 中可以视为常数。

通过观察 \alpha-p 图像，我发现这个超越函数在 (0.5,0.9) 几乎为线性，线性回归得到 p(\alpha)\approx 0.7002\alpha +0.1511，在 (0.5,0.9) 的误差在小数点后三位，几乎可以忽略。这样，计算复杂度时就没有必要解超越方程了。

所以，替罪羊树维护的 K‑D Tree 复杂度是有保障的，只是比根号略微高一点。这就是为什么大家认为其复杂度错误但多年来没有人成功地 Hack 的原因。

一个伪证的批驳

在上述介绍替罪羊树维护 K‑D Tree 的文章 aaron0919 的 P14312 【模板】K-D Tree の题解中，其证明最重要的是这个式子：

\sum_{i=0} ^{\frac{h}{2}} 2^i \approx 2^{\frac{h}{2}} \approx 2 ^{\frac{\log _2 n}{2}} = \sqrt n

现不考虑其没带 \Theta 或 \mathcal{O} 的不严谨。其核心错误在于第二个约等号：

2^{\frac{h}{2}} \approx 2^{\frac{\log _2 n}{2}}

由于替罪羊树是只能保证 \alpha‑高度平衡，树高可以达到

h=\log _{\alpha^{-1}} n = \frac{\log _2 n}{\log _2 {(\alpha ^{-1})}}

则代入得

2^{\frac{h}{2}}= 2^{\frac{\log _2 n}{2\log _2 {(\alpha ^{-1})}}} =n ^{\frac{1}{2\log _2 {(\alpha^{-1})}}}

比如代入 \alpha=0.6，得到复杂度约为 \Theta(n^{0.68})；代入 \alpha=0.75，得到复杂度约为 \Theta(n^{1.20})：这个结果明显劣于上面的分析，更不是其所称的根号。而且即使修正后 \alpha 稍大时复杂度就超过平凡的上界 \mathcal{O}(n)，没有很大的实际价值。

替罪羊树的重构复杂度证明

替罪羊树满足

\max(\text{size}(left), \text{size}(right)) \le \alpha \cdot \text{size}(parent)

否则会进行重构。

重构完成的瞬间，子树满足 \frac{1}{2}‑重量平衡，左右子树大小相差最多为 1。

我们现在考虑：从一个刚刚重构好了的满足 \frac{1}{2}‑重量平衡的子树，至少要插入 d 给点才会使得这个这个子树不满足 \alpha‑重量平衡。

设当前子树大小为 n，其中左子树大小就为 \lceil{\frac{n-1}{2}}\rceil，右子树大小为 \lfloor\frac{n-1}{2}\rfloor。最极端的情况是所有的都插入到同一个左子树中。那么当该子树不满足 \alpha‑重量平衡时，满足：

\begin{align*} \left\lceil{\frac{n-1}{2}}\right\rceil+s&>\alpha (n+s)\\ \end{align*}

将 \left\lceil{\frac{n-1}{2}}\right\rceil 放缩为 \frac{n}{2}。

\begin{align*} \frac{n}{2}+s&>\alpha (n+s)\\ \frac{n}{2}+s&>\alpha n+ \alpha s\\ (1- \alpha)s &>(\alpha-0.5) n\\ s &> \frac{\alpha-0.5}{1-\alpha} n \end{align*}

这是一个下界。记 c=\frac{\alpha-0.5}{1-\alpha}。

而重建一个大小为 n 的子树所用时间为 \Theta(n\log n)。（按 nth_element 的平均复杂度为线性计算，如果追求严格可以使用 median of medians 算法，但常数较大）

得到重构的代价为 \frac{\Theta(n \log n)}{s} \lt \frac{\Theta(n \log N)}{cn}=\mathcal{O}(\frac{(1-\alpha)\log N}{\alpha-0.5})，其中 N 为整棵树最多的结点树，显然 N \ge n。

这样，单次重构时路径上每个点的均摊代价为 \mathcal{O}(\frac{(1-\alpha) \log N}{\alpha-0.5})。

而插入时还经过 \log _{\alpha ^{-1}} N 个点，故总共的代价为 \mathcal{O}(\frac{1-\alpha}{\alpha-0.5}\log N \log_{\alpha^{-1}} N)。证毕。

由于插入找到一个数位置的复杂的为 \mathcal{O}(\log _{\alpha ^{-1}} {N})，相对于重构可以忽略。

\alpha 的最优取值

我们求出了修改、查询的复杂度，这可以指导我们求 \alpha 的理论最优值。

假设插入、查询比例为 1:1，则我们可以得到一个函数：

C(n,\alpha)=n ^{p(\alpha)} + \frac{1-\alpha}{\alpha -0.5} \log _2 n \log _{\alpha ^{-1}} {n}

在固定 n=10^5 时，\alpha \approx 0.63 时最优。

实践中可以根据表现和常数调参，建议以 \alpha = 0.6= \frac{3}{5} 开始。

高维情况

从一个上述四类点向下深度为 k 会划分成从一个 k 维超立方体划分成 2^k 个子 k 维超立方体，大小依次为 (\alpha+(1-\alpha))^k 二项式展开的结果。

若 k 为奇数，最大的 2^{k-1} 个为 \binom{k}{0} 个 \alpha ^k，\binom{k}{1} 个 \alpha ^{k-1} (1-\alpha)，一直到 \binom{k}{\frac{k-1}{2}} 个 \alpha ^{\frac{k+1}{2}}(1- \alpha)^{\frac{k-1}{2}}。

复杂度为

T(n)= \sum _{i=0} ^{\frac{k-1}{2}} \binom{k}{i} T(\alpha^{k-i}(1-\alpha)^{i}n) + \Theta (1)

Akra‑Bazzi 方程为：

\sum _{i=0} ^{\frac{k-1}{2}} \binom{k}{i} (\alpha^i(1-\alpha)^{k-i}) ^p =1

这个超越方程没有初等通式解，也不好分析。考虑三维情况：

\alpha ^{3p} + 3(\alpha ^2 (1-\alpha))^p=1

这也没有初等通式解。代入 \alpha=0.6，解得 p \approx 0.76；代入 \alpha=0.7，解得 p \approx 0.85：这时复杂度已经很高了，建议根据实际表现适当调小 \alpha。

当 k 为偶数时，可得递归式

T(n)= \sum _{i=0} ^{\frac{k}{2}-1} \binom{k}{i}T( \alpha ^{k-i}(1-\alpha)^in) + \frac{1}{2} \binom{k}{\frac{k}{2}} T(\alpha^{\frac{k}{2}} (1-\alpha)^{\frac{k}{2}}n)

而 k 为任意值时实在难以分析，且 k 较大时和暴力差距不大，故略去。

一些留给读者的开放问题

建树时可能还有另一种方法——方差划分——这种方法使用替罪羊树维护是否能证明其复杂度有保障？
本文表明不完全平衡的 K‑D Tree 复杂度仍然可能有保证，那么能否换用其他的平衡树维护？

参考资料

Akra M , Bazzi L .On the Solution of Linear Recurrence Equations[M].Kluwer Academic Publishers,1998.
Galperin I , Rivest R L .Scapegoat Trees[J].DBLP, 1993.DOI:10.1145/313559.313676.
OI Wiki 上的 K‑D Tree 和替罪羊树的复杂度证明
Leighton T. Notes on better master theorems for divide-and-conquer recurrences. MIT Lecture Notes, 1996. 这是一份 MIT 的讲义。可以在 MIT 官方课程网站获得。
一个关于 Akra‑Bazzi 定理适用条件的问答：asymptotics - Why does Akra-Bazzi need that toll-function g is bounded? - Computer Science Stack Exchange
aaron0919 的 P14312 【模板】K-D Tree の题解
GONGGONGJOHN 的从主方法到Akra-Bazzi定理

本文可能火药味比较足，敬请谅解。如有错误，欢迎批评指正。