参考资料：
KDT小记
K-D Tree，处理高维数据的利器
给的例题有点大份了，没写几个题，剩下的以后再说。
\(\text{KDT}\)
\(\text{K-D Tree}\)，是一种能在 \(k\) 维空间内维护点信息的数据结构，一般常用的就是二维平面内，即 \(K=2\)。
\(\text{KDT}\) 的构建
\(\text{KDT}\) 的构建就是每次尽可能选取最中心的点，然后分治整个平面，那么对于选取方式，我们就有两种实现方法：
-
轮流划分：即按照 \(1,2,\dots,K\) 的顺序轮流选取维度中位数作为中心点。
-
方差划分：按照每个维度的方差，优先在方差最大的维度选择中心点当做整体中心点。
在某些情况下，第二种划分会比第一种快上不少，如果图方便的话写第一种也挺好的。
还有一个注意点，对于选取中位数，我们使用 nth_element 函数，就可以在 \(O(n)\) 的时间内找到中位数并划分为左右两部分。
关于 nth_element 的具体实现，大概是类似快排，每次随机选取一个数作为 \(\text{key}\)，确定排名后选择向哪一侧继续划分，由于每次是随机选数，所以期望复杂度是 \(O(n)\)。
回到正题，那么建树的复杂度就是 \(T(n) = 2T(n/2) + O(n)\)，由主定理可得，总复杂度是 \(O(n\log n)\)。
\(\text{KDT}\) 领域查询
这个最经典的题就是平面最近点对了，我们考虑暴力枚举每个点作为一端，每次到 \(\text{KDT}\) 中去查询，其流程大概为：
-
用当前节点更新答案。
-
如果答案一定小于子树内的最小值，那么跳出。
-
选择左右儿子可能更近的一个走过去，然后再走另一个。
对于点到子树最小值，我们找到该子树代表的矩形，求点到矩形的距离即可。
如果采用的是 \(\text{Leafy}\) 式结构，就不需要第一步了。
\(\text{KDT}\) 的插入
由于 \(\text{KDT}\) 是基于 nth_element 的相对大小基本保证复杂度的，所以并不能支持动态在一棵树上插入一个点，我们考虑换种方式。
方案一是我们暴力插入，然后考虑类似替罪羊树的方法，当左右子树不平衡时重构子树，这样比较难写，而且重构系数每次需要重新计算。
方案二我们可以开两棵树，并设一个阈值 \(B\)，当第二棵树每次攒够 \(B\) 个点就和第一棵树合并，这样当然能快很多，但是还是需要考虑阈值，并且要写合并函数。
方案三我们可以二进制分组，具体地，开 \(\log\) 棵 \(\text{KDT}\)，每次有两棵大小相同的就合并起来，可以类似二项堆证明总复杂度是 \(O(nlog^2 n)\)，比上面两种要优秀很多，而且用 vector 实现的话也比较简单，就是空间常数可能会比较大。
\(\text{KDT}\) 的矩形操作
考虑类似线段树的做法，只有每次查询矩形完全包含当前矩形再更新信息，而与查询矩形无交的肯定没有贡献，于是与复杂度挂钩的就只有与查询矩形有交的点。
我们不妨将矩形每条边拆开来看，令 \(T(n)\) 表示大小为 \(n\) 的 \(\text{KDT}\) 中这条边能穿过多少区域，从轮换划分来看，将相邻两轮划分看做一组，那么一组划分中，这条边最多只会经过两个区域，而每个经过区域都起码是原来的 \(\frac{1}{4}\)，于是有 \(T(n) = 2T(n/4) + O(1)\)，由主定理可得总复杂度为 \(O(\sqrt n)\)，于是 \(\text{KDT}\) 单次矩形操作的复杂度是 \(O(\sqrt n)\)。
注意：这里这样划分的话边缘处可能会有区域重叠，需要去掉这种情况的话将平面和矩形整体放大即可。
进一步的，我们可以推广到 \(K\) 维空间内，\(\text{KDT}\) 一次查询的复杂度是 \(O(n^{1-\frac{1}{k}})\)。
其实 \(\text{KDT}\) 都可以采用类似线段树的结构实现，所以线段树的技巧放到 \(\text{KDT}\) 上也是可以使用的，注意时空限制即可。