KDtree是一种很好用的数据结构，在维护多维信息的时候有奇效。
当维护 \(k\) 维信息的时候单次时间复杂度是 \(n^{\frac{k-1}{k}}\),一维另作讨论.
这里拿二维来举例子
把二维平面竖着切一刀，选择按 \(x\) 坐标排序中位数的点来切。
剩下的就被分成了两部分，递归下去的时候按这一部分的 \(y\) 排序来切，再向下递归的时候按这一部分的 \(x\) 排序来切...
维护区间信息的话有点类似于线段树。
多刷刷题就好了。
某枫举过一个例子：
当维护的信息多一维的时候，写树套树的话码量，常数，调试难度会上升一个数量级。
但是KDtree只用增加变量，修改一下排序方式。
哪个更方便显而易见.
原文：https://www.cnblogs.com/wljss/p/13154611.html