同步阅读进度，多语言翻译，过滤屏幕蓝光，评论分享，更多完整功能，更好读书体验，试试 阅读 ‧ 电子书库
范围查询
有一个矩形区域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维的正方体。
输出
在这个区域内的所有点，不要求按顺序输出。
假设
查询的范围维度是数据的维度保持一致。
请支持我们，让我们可以支付服务器费用。
使用微信支付打赏
