正交范围查询

问题族 ​

在计算几何公理库计算几何问题Computational geometry problem以点、线段、多边形等几何对象为输入并要求组合或数值几何输出的问题族。中，给定 (P\subset\mathbb R^d) 与轴对齐盒 (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 结构都至少要为这两个输出付出 (\Omega(k)) 时间。

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

维数与结构边界 ​

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

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

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

参考资料

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