又是一个不需要证明的东西，复杂度基本玄学。
具体来说 K-D Tree 是解决高维问题的一个数据结构（其实一般是二维）。
K-D Tree 本质上是一棵二叉搜索树，其的基本思想就是遍历整个状态空间加剪枝。
设问题维度是K，其单次查询的复杂度大概是 \(O(n^{\frac{K-1}{K}})\)。

我们一般采用每次随机找一个维度，以这个维度排序，且以这个维度的中位数为根的方法。
这种方法基本上不会被卡。
一般来说我们维度的选择就是从 1-K 反复循环进行的。

这个就具体问题具体分析了，说几个经典问题吧。

找距离一个坐标最远的点。
这个比较简单，维护每颗子树里每一维最大和最小的值，然后一一配对取最大值就可以了。

这个就比较妙了。
我们依旧维护每颗子树里每一维最大和最小的值;
然后对于每一维我们找到理想状态下距离最近的点，加入答案中。
其实本质上是 A*。
算了，给个代码实现吧。

  1. int getmin(int rt, int x, int y, int res = 0) {
  2.     for(register int i = 0; i < 2; ++i) {
  3. 	    if(i == 1) x = y;
  4. 	    res += max(0, tr[rt].mi[i] - x);
  5. 	    res += max(0, x - tr[rt].mx[i]);
  6. 	}
  7.     return res; 
  8. }

一般来说 K 不会很大。
这个我们可以开个小根堆，初始时堆里有 K 个元素。
查询时每次替换最小的那个就可以了。

主要利用的是替罪羊的思想。
插入的话我们直接向平衡树那样插入就可以了。
维护平衡因子，适时推翻重建以维护平衡。
（暂时没有写过）

版权声明：本文为longdie原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/longdie/p/K-DTree.html