K-D Tree 学习笔记
又是一个不需要证明的东西，复杂度基本玄学。
具体来说 K-D Tree 是解决高维问题的一个数据结构（其实一般是二维）。
K-D Tree 本质上是一棵二叉搜索树，其的基本思想就是遍历整个状态空间加剪枝。
设问题维度是K，其单次查询的复杂度大概是 \(O(n^{\frac{K-1}{K}})\)。
K-D Tree 的建树方法
我们一般采用每次随机找一个维度，以这个维度排序，且以这个维度的中位数为根的方法。
这种方法基本上不会被卡。
一般来说我们维度的选择就是从 1-K 反复循环进行的。
K-D Tree 的查询方法
这个就具体问题具体分析了，说几个经典问题吧。
最远点
找距离一个坐标最远的点。
这个比较简单，维护每颗子树里每一维最大和最小的值，然后一一配对取最大值就可以了。
最近点
这个就比较妙了。
我们依旧维护每颗子树里每一维最大和最小的值;
然后对于每一维我们找到理想状态下距离最近的点，加入答案中。
其实本质上是 A*。
算了，给个代码实现吧。
int getmin(int rt, int x, int y, int res = 0) {
for(register int i = 0; i < 2; ++i) {
if(i == 1) x = y;
res += max(0, tr[rt].mi[i] - x);
res += max(0, x - tr[rt].mx[i]);
}
return res;
}
K远点
一般来说 K 不会很大。
这个我们可以开个小根堆，初始时堆里有 K 个元素。
查询时每次替换最小的那个就可以了。
动态插入
主要利用的是替罪羊的思想。
插入的话我们直接向平衡树那样插入就可以了。
维护平衡因子，适时推翻重建以维护平衡。
（暂时没有写过）
