正交范围查询

形式陈述 ​

问题族 ​

在计算几何公理库计算几何问题Computational geometry problem以点、线段、多边形等几何对象为输入并要求组合或数值几何输出的问题族。中，给定 $P\subset {\mathbb{R}}^d$ 与轴对齐盒；每个坐标轴上的端点比较采用全序公理库全序Total order · Linear order任意两个元素都可比较的偏序。。查询盒写为 $Q=\prod _j[a_j,b_j]$。Reporting 输出 $P\cap Q$，成本必须含 $k=|P\cap Q|$；counting 只返回 $k$，emptiness 返回布尔值，semigroup query 聚合权重。

二维地图点集在矩形视窗内报告是标准实例。边界点是否计入由闭区间约定决定；旋转矩形、圆盘与半空间不是 orthogonal 查询，不能沿用坐标轴分解。

二维 Range Tree ​

主树按 $x$ 坐标建立平衡搜索树，每个节点保存其子树点按 $y$ 排序的关联表。查询 $[x_1,x_2]\times [y_1,y_2]$ 先找两个 $x$ 端点的分叉位置，把横向范围分解为 $O(\log n)$ 个规范子树，再在各关联表中二分 $y$ 区间。

点集

$$(1,4),(2,1),(3,3),(5,2)$$

查询 $[2,5]\times [2,3]$ 时，横向候选是后三点，关联表再按 $y$ 过滤出 $(3,3),(5,2)$，输出 $k=2$。任何 reporting 结构都至少要为这两个输出付出 $\mathrm{\Omega }(k)$ 时间。

每个点出现在主树一条祖先路径的关联表中，总空间为 $O(n\log n)$。查询访问 $O(\log n)$ 张表，每表一次二分，朴素 counting 为 $O({\log }^{2}n)$，reporting 为 $O({\log }^{2}n+k)$。Fractional cascading 共享后续定位，把二维报告降到 $O(\log n+k)$，但不消除输出项。

直觉

轴对齐查询可沿每个坐标独立切分。Range tree 先把横向区间分解成少量完整子树，再在各子树预存的纵向次序中筛选；分数级联还能让同一纵向端点在这些相关目录之间连续传递，而不重复二分。

例子与边界

二维视窗查询若命中 $k$ 个点，任何结构都至少要输出这 $k$ 项；计数接口则可以只聚合规范子树摘要。边界取开区间还是闭区间、重复坐标怎样打破平局，以及点集能否动态更新，都会改变端点处理与维护成本。

维数与结构边界 ​

$d$ 维递归 range tree 的典型空间达到 $O(n{\log }^{d-1}n)$。只有 $d$ 固定时，才能把指数依赖藏进多对数记号；高维中必须显式写出维数。

Kd-tree 的性能依点分布与查询形状，最坏界不同于 range tree；priority search tree 针对三边范围。报告与计数也有不同空间权衡，静态关联表不自动支持点插删。把这些结构统称“空间树”会丢失可比较的保证。

semigroup query 还取决于权重运算是否可逆。若只能结合不能相减，不能随意把 counting 的前缀差技巧搬来；接口必须连同代数假设一起说明。

推论与应用

正交范围查询是地图视窗、数据库多列过滤和几何报告结构的基础接口。Range tree、k-d tree 与 priority search tree 分别选择不同的空间、查询形状和最坏界；应用时应先固定 reporting、counting 或 semigroup 聚合，而不是只按“多维搜索”选结构。

参考资料

• Jon Bentley, “Multidimensional Binary Search Trees,” CACM, 1975.
• Agarwal, Erickson, “Geometric Range Searching and Its Relatives,” 1999.