范围树

二维结构 ​

主平衡树按 $x$ 坐标组织点。每个节点 $v$ 的 canonical subset 是其子树点集，并保存按 $y$ 排序的关联数组 $A_v$。构建可自底向上归并，空间和预处理为 $O(n\log n)$。

查询矩形 $[x_1,x_2]\times [y_1,y_2]$ 时，主树把 $x$ 区间分解为 $O(\log n)$ 个不交 canonical subsets；在每个 $A_v$ 中二分 $y_1,y_2$，报告其间元素。因此查询为 $O({\log }^{2}n+k)$，其中 $k$ 是输出点数。分数级联公理库分数级联fractional cascading在相关有序目录间建立采样桥，使一次完整二分后可常数时间转移位置。共享这些二分，可降为 $O(\log n+k)$。

仓储检索例子 ​

点表示商品的价格与库存量。查询“价格落在区间且库存高于阈值”的商品时，价格范围先选出少量完整子树，再在各自库存目录中定位边界；无需扫描目录中的其他价格点。

维数与动态边界 ​

递归到固定 $d$ 维，空间为 $O(n{\log }^{d-1}n)$，典型查询 $O({\log }^{d}n+k)$；把 $d$ 隐藏成常数后不能再宣称高维高效。动态插入会更新主树祖先的多个关联目录，不能沿用静态成本。报告必须含 $k$，计数结构则可只存摘要，二者不是相同空间权衡。

构建与 canonical 分解 ​

主树若按中位数构造，左右子树关联数组已排好，可在线性时间归并成父数组。每层全部数组总长度 $n$，共 $O(\log n)$ 层，因此空间和构建归并工作 $O(n\log n)$，而不是为每节点独立排序的更高成本。

一维区间在平衡树中由分裂节点两侧的 maximal fully-contained subtrees 表示，数量 $O(\log n)$ 且互不重叠。这一 canonical 分解保证报告点不会重复。k-d tree公理库k-d Treek-d tree · kd-tree递归按坐标切分空间，并以包围区域剪枝多维范围或最近邻查询。用空间区域剪枝，通常更省存储但最近邻/范围查询最坏保证不同。

一次矩形查询的节点轨迹 ​

设主树根键为 50，查询 $x\in [20,68]$。先找到两条搜索路径的分裂节点；沿左边界向下时，每次向左走，就把当前节点的右子树作为完整 canonical subset；沿右边界对称处理左子树。边界路径上的单点另行检查，因此所取子树两两不交且并集恰为 $x$ 区间内所有点。

对每个完整子树 $v$，在 $A_v$ 中用两个 lower/upper bound 得到 $y$ 合法的连续切片。若只计数，可累加端点差；若报告，逐个输出该切片，故时间必须带 $+k$。关联数组若只存坐标而没有点标识，重复坐标会丢失对象，实际记录应包含稳定 ID。

静态构建的状态顺序为：先按 $x$ 中位数递归建主树，再自底向上归并孩子的 $y$ 数组。每一层恰复制 $n$ 条记录，$O(\log n)$ 层给出 $O(n\log n)$ 空间；这不是“每个节点都存全体点”，而是每个点在每个深度出现一次。

动态范围树要在 $O(\log n)$ 个祖先目录中插入或删除同一点。若关联目录只是普通数组，一次更新会线性搬移；需要动态平衡目录、分数级联的动态版本或批量重建，不能直接继承静态查询表的成本。

若矩形边界采用闭区间，左端用 lower_bound(y1)，右端用 upper_bound(y2)；若采用半开区间 $[y_1,y_2)$，两端都用 lower_bound。重复坐标恰落在边界时，这个选择决定是否报告，必须与查询接口保持一致。

高维递归把每个 canonical subset 再建一棵低一维范围树。每升一维多出一层 $\log n$ 空间和查询分解，所以“固定维”是复杂度成立的量词；当维数随输入增长时，这种递归很快超过线性扫描。

参考资料

• Jon Bentley, Multidimensional Divide-and-Conquer, CACM, range searching work.
• Mark de Berg et al., Computational Geometry, range trees chapter.