KD-Tree 学习笔记

SDOI2010 捉迷藏

对于i=1...n,求曼哈顿距离距离i最近和最远的点的距离分别是多少。

思路

KD-Tree 的模板题目。

KD-Tree，实际上就是对一个多维空间进行不断的划分，在一维上类似于二叉搜索树。

如果是多维的，我们可以每一次只划分一维，然后这样不断轮流划分不同的维度。

具体的，对于当前维度的划分，我们最优秀的策略就是取所有点按照当前维度排序之后从中点划分开来，这样可以保证整颗树尽量的平衡。

对于每一次划分应该选择哪个维度，我们其实可以选择维度方差最大的那个维度进行划分，这样可以保证复杂度尽量地优秀。

这个题目需要寻找平面内最近/最远点，考虑如何实现实现上述查询，我们可以计算出当前的点距离当前矩形的左右儿子的最小/最大距离，优先递归答案可能会更加优秀的那个点，如果目前的区间的最优的答案都比目前得到的最优答案要劣，那么我们就可以停止递归了。

不难发现上面的查询操作本质上是一个搜索+剪枝，KD-Tree独特的构造方法使得一般情况下复杂度为(log n)，最坏复杂度为(sqrt n)。

SJY摆棋子

动态加点，动态询问距离某一个点最近的点是哪一个。

思路

由于需要动态加点，这会导致KD-Tree的结构不够稳定，于是我们需要用到替罪羊树的思想，即给每一个点设定一个平衡因子(alpha)，一旦在加入了某一个点之后有一个点不满足平衡性，即一个点左儿子或者右二子的size/这棵树的size大于平衡因子，则暴力重构。利用势能分析，当平衡因子(alpha)取(0.75)的时候复杂度接近(nlog n)。

维护多维区间信息

当KD-Tree用来维护多维区间信息的时候，复杂度不见得比暴力或者线段树优秀，但是空间的开销是线性的。

如果我们需要用KD-Tree来维护多维区间信息，一个必须的条件是我们必须要知道所有的关键点，然后对这些关键点建立KD-Tree。

这些关键点的作用实际上是将k维空间不断划分成那些对后面的询问/修改有用的区间，这些关键点自己本身并不需要存储在KD-Tree中，实际上就是一颗优化了空间的划分和树型结构的线段树，在大部分操作上面都和线段树相当。

单点修改：直接修改KD-Tree上所有包含了这个点的节点即可。
区间操作：需要适当的剪枝，例如在查询最大值的时候判断左右儿子的最大值和目前的最大值的关系，从而return。