KDtree是一种很好用的数据结构，在维护多维信息的时候有奇效。

当维护 \(k\) 维信息的时候单次时间复杂度是 \(n^{\frac{k-1}{k}}\),一维另作讨论.

这里拿二维来举例子

把二维平面竖着切一刀，选择按 \(x\) 坐标排序中位数的点来切。

剩下的就被分成了两部分，递归下去的时候按这一部分的 \(y\) 排序来切，再向下递归的时候按这一部分的 \(x\) 排序来切...

维护区间信息的话有点类似于平衡树。

多刷刷题就好了。

某枫举过一个例子：

当维护的信息多一维的时候，写树套树的话码量，常数，调试难度会上升一个数量级。

但是KDtree只用增加变量，修改一下排序方式。

哪个更方便显而易见.