阅读 ‧ 电子书库

范围查询

有一个矩形区域R[x_low,y_low,x_high,y_high]，以及一个点集P，请问P中哪些点是在矩形区域R中的呢？穷举算法会检查所有的点，花费的时间为O(n)，我们能够做得更好么？使用kd树，我们将会阐述如何高效地解决在笛卡儿平面上的范围查询。

r是在R中的点的个数。当然，当点是d维时，这个问题就成了d维范围查询，能够在O(n^1-1/d+r)的时间内得到解，如图9-24所示。

输入/输出

输入

广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元

一个d维的点集P和一个d维的正方体。

输出

在这个区域内的所有点，不要求按顺序输出。

假设

查询的范围维度是数据的维度保持一致。