正交范围查询

形式陈述 ​

问题族 ​

在计算几何理路计算几何问题Computational geometry problem以点、线段、多边形等几何对象为输入并要求组合或数值几何输出的问题族。中，先固定正整数维数 $d$。输入是一份含 $n$ 条记录的静态点表 $P$，每条记录给出 ${\mathbb{R}}^d$ 中的有限坐标和唯一 ID。查询输入是轴对齐盒 $Q=\prod _j[a_j,b_j]$，每个坐标轴上的端点比较采用全序理路全序Total order · Linear order任意两个元素都可比较的偏序。。下文以 $P\cap Q$ 简写坐标落入 $Q$ 的记录集合。Reporting 输出 $P\cap Q$，成本必须含 $k=|P\cap Q|$；counting 只返回 $k$，emptiness 返回布尔值。若不同记录坐标相同，用稳定 ID 区分，计数与报告保留每条记录。空输入直接给空报告或计数零；以下对数渐近界针对 $n\ge 2$，更小输入直接检查。

聚合版本额外给每条记录权重，取值于一个交换半群理路半群Semigroup带有结合二元运算的集合。，并返回命中权重之和。交换律让无序点集的聚合不依赖枚举顺序；只有结合律的字符串连接会因 ab 与 ba 而不同，必须另定顺序后再谈相应查询。半群未必有单位元，所以空命中返回单独的空标记；若接口要求它仍是权重域中的元素，需额外指定幺元。也允许一侧端点为无穷的查询变体，例如三边区域 $[a,b]\times (-\mathrm{\infty },c]$。

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

二维报告的一种实现 ​

范围树理路范围树range tree以主坐标搜索树和节点关联目录支持固定维正交范围查询。的主树按 $x$ 坐标建立平衡搜索树，每个节点保存其子树点按 $y$ 排序的关联表。查询 $[x_1,x_2]\times [y_1,y_2]$ 先找两个 $x$ 端点的分叉位置，把横向范围分解为 $O(\log n)$ 个规范子树，再在各关联表中用二分查找理路二分查找Binary search在有序数组中反复排除一半候选区间的查找算法。定位 $y$ 区间。

点集

查询 $[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)$，但不消除输出项。