范围树

主树把一个坐标区间拆成少量互不重叠的规范点集，每个点集提前保存另一坐标的有序目录。查询因而不再逐点做二维判断，而是在 $O(\log n)$ 个完整子树中分别截取连续的纵向切片；输出点只会属于其中一个切片。

仓储检索例子 ​

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

维数与动态边界 ​

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

范围树在主树节点保存整个下一坐标目录，目录大小随子树增长。它不满足常数大小摘要的搜索树增强定理理路搜索树增强定理与方法Search-tree augmentation区分可逐层重算的子树摘要与旋转后只需局部修复的中序聚合，并据此维护增强搜索树。所需的常数时间合并条件，不能据该定理推出一次旋转或更新只需常数工作；这里应直接计入各目录的合并、存储与修改成本。

构建与 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$ 空间和查询分解，所以“固定维”是复杂度成立的量词；当维数随输入增长时，这种递归很快超过线性扫描。