$\texttt{k-D Tree}$(KDT , k-Dimension Tree) 是一种可以高效处理 $k$ 维空间信息的数据结构。

在结点数 $n$ 远大于 $2^n$ 时，应用 $\texttt{k-D Tree}$ 的时间效率很好。

在算法竞赛的题目中，一般有 $k=2$。在分析时间复杂度时，将认为 $k$ 是常数。

k-D Tree 数据结构

建树

$\texttt{k-D Tree}$ 具有二叉搜索树的形态，二叉搜索树上的每个结点都对应 $k$ 维空间内的一个点。其每个子树中的点都在一个 $k$ 维的超长方体内，这个超长方体内的所有点也都在这个子树中。

假设我们已经知道了 $k$ 维空间内的 $n$ 个不同的点的坐标，要将其构建成一棵 $\texttt{k-D Tree}$，步骤如下：

• 若当前超长方体中只有一个点，返回这个点对应编号。
• 选择一个维度，将当前超长方体按照这个维度分成两个超长方体。
• 选择切割点：在选择的维度上选择一个点，这一维度上的值小于这个点的归入一个超长方体（左子树），其余的归入另一个超长方体（右子树）。
  • 这里有一点注意事项。分割点必然选取这一维度的坐标中位数的对应点，就是排序后中间的那个点，但是排序的复杂度为 $\Theta(n\log_2n)$，切割 $\Theta(\log_2n)$ 次，时间复杂度是 $\Theta(n\log_2^2n)$。
  • 但是排序实际上浪费了许多信息，我们只需要中间点即可。
  • $\texttt{STL}$ 提供了一个函数 std::nth_element 可以实现把整个序列分成三部分：左边、中间、右边，并且保证左边不大于中间，右边不小于中间，正好符合要求。std::nth_element 基于分治思想实现，单次操作 $n$ 个项的时间复杂度为 $\Theta(n)$，切割 $\Theta(\log_2n)$ 次，时间复杂度是 $\Theta(n\log_2n)$，更快了。
• 将选择的点作为这棵子树的根节点，递归对分出的两个超长方体构建左右子树，维护子树的信息。

其实按照上述步骤建树以后，$\texttt{k-D Tree}$ 操作的时间复杂度的影响因素只有两个：

1. 树的平衡度；
2. 每次选择的维度；

下面着重讨论这两个方面。

树的平衡度

如果树不平衡（甚至树直接退化成了链），那么单次操作的时间复杂度为 $\Theta(n)$，显然太慢。

于是考虑解决树不平衡的问题。$\texttt{k-D Tree}$ 之所以会不平衡，是因为我们会往里面插入新的结点，如果光往左子树里插，就会导致树的左子树“粗壮”。发现这与二叉搜索树的情形类似，于是考虑用类似的方法解决问题。

常用的是替罪羊树的方法：把树拍扁重建。

每次选择的维度

有多种方法选择维度。

1. 不选择
   这怎么可能是 $\texttt{k-D Tree}$，肯定会爆炸的。
2. 随机选择
   这个建树的复杂度比较玄学，一般不容易通过题目。
3. 每次轮换选择
   这个写起来方便，但是容易被特殊数据卡死，时间复杂度为 $\Theta(n\log_2n)$。
4. 每次选择方差最大的维度
   这个最科学，并且理论上这样使得 启发式搜索 的耗时最短，但是建树时候要计算方差，常数较大，容易被卡（本质上是时间复杂度变成了 $\Theta(nk\log_2n)$）。

插入操作

比较简单，正常的插入操作，就是动态开点的树。

查询操作

视情况而定，具体操作具体分析，大部分题目的查询操作都是启发式搜索，某些卡树套树空间，卡 CDQ 分治的毒瘤题除外。

题目推荐

洛谷 P4148
洛谷 P2479