解决什么问题

Range Tree（区域树？范围树？）是为了解决在多维空间中对点集进行正交范围查询（orthogonal range query）的问题，问题定义如下：

给定一组 P 中的 n 个点，以及一个查询矩形 ，快速报告或计数落在该矩形范围内的所有点。

在二维情况下，最直观的做法是对 x 和 y 均做平衡树索引，但直接维护两棵独立的树无法做到联合查询。Range Tree 的思想是：

• 在主树（primary tree）上按照 x 均衡拆分
• 在每个主树节点上，维护一个次级树，对该节点对应子树内的所有点按照 y 再做一次平衡树

这样，查询时先在主树中用 x 将问题分解为 个子区间，再在每个子区间对应的次级树中以 y 答案，整体时间为 （k 为输出点数）。

数据结构

一个二维 Range Tree 是一棵平衡二叉搜索树（如 AVL 或红黑树），每个节点 v 存储：

1. 关键字：该节点对应的点的 x 坐标，或子区间的中点
2. 左/右子指针：指向左右子树
3. 附属结构：一棵同样平衡的 BST，按照 y 坐标 存储了以 v 为根的整个子树中的所有点

Range Tree 的构建

给定输入n个点，对 n 个点一次性建树：

1. 按 x 排序，取中点作根，递归构建左右子树
2. 在回溯时，合并左右子树中的点列表，按 y 排序，构建当前节点的次级树

空间复杂度： 主树用 ，各节点次级树总共存储 个节点 ⇒

范围查询

1. 定位“分裂节点” ：从根节点开始，沿二叉搜索树按 x 比较走下去，直到到达第一个满足 的节点 v。该节点称为“分裂节点”（split node）。

2. 此时，左子树的所有节点已经满足 。在左子树搜集全包含子区间（比较 ），从 开始，沿搜索路径向下遍历：

   1. 若当前节点 的 ，则其 右子树 完全位于 范围内，于是在该右子树对应的次级树 中执行一次 1D 范围查询（查找所有 的点）；检查当前节点 的 是否满足范围查询要求；递归查询当前节点左子树。
   2. 否则，递归查询当前节点右子树。

3. 对右子树进行类似搜索。

4. 将第 2 步和第 3 步中所有次级树查询的输出汇总，即为最终落在矩形内的所有点。

时间复杂度

• 查找分裂节点：
• 左右两条路径：各自沿深度 走访节点，每遇到一个“全包含子树”就对其次级树做一次 1D 查询。次级树查询成本 ，其中 k_i 是该次级查询输出的点数。
• 总体 。其中 为所有输出点总数。

K 维拓展

未完待续

Fractional Cascading优化

未完待续

---

参考资料

M. de Berg, O. Cheong, M. J. van Kreveld, and M. H. Overmars, Computational Geometry: Algorithms and Applications, 3rd ed. Berlin, Germany: Springer, 2008, ISBN 978-3-540-77973-5.