注：\(K-D\Tree\)的应用中由于大量用到了\(dfs\)剪枝，所以通常不是正解。但是由于他相当好写，而且通常跑的不慢，所以也广为流传。感觉像是一种半骗分思路。下文简称其为\(KDT\)。一、\(K-D\Tree\)我们都知道\(2D,3D\)表示二维、三维，所以\(KDT\)也很好理解，就是\(K\)维的

咕咕咕。学会了一点了。KDT维护了\(k\)维空间中的超长方体。每个结点及其子树都在同一超长方体中。KDT的实现与平衡树类似（其实在\(k=1\)时就是另类的平衡树，只不过不太优秀）。树上的每个结点都对应着\(k\)维空间中的一个点。然后随便维护一下信息就可以支持\(k\)维超长方体查询信