有一个矩形区域R[xlow,ylow,xhigh,yhigh]，以及一个点集P，请问P中哪些点是在矩形区域R中的呢？穷举算法会检查所有的点，花费的时间为O(n)，我们能够做得更好么？使用kd树，我们将会阐述如何高效地解决在笛卡儿平面上的范围查询。
r是在R中的点的个数。当然，当点是d维时，这个问题就成了d维范围查询，能够在O(n1-1/d+r)的时间内得到解，如图9-24所示。
图 9-24 范围查询详解输入/输出
输入
一个d维的点集P和一个d维的正方体。
输出
在这个区域内的所有点，不要求按顺序输出。
假设
查询的范围维度是数据的维度保持一致。