计算几何中的区间树（Interval Tree）
字数 3682 2025-12-18 14:57:40

计算几何中的区间树（Interval Tree）

我们开始探索计算几何中一种用于高效处理区间查询的数据结构——区间树。它的核心问题是：给定平面上的一组水平线段（或更一般地，轴对齐的矩形在某一维上的投影），如何快速找出所有与一条给定垂直线相交的线段？或者，给定一组区间（一维线段），如何快速找出所有与一个给定点（或另一个给定区间）重叠的区间？区间树为解决此类问题提供了优雅的解决方案。

让我们一步步构建这个知识体系：

第一步：问题定义与直观思路

首先，将问题形式化。我们有一组 n 个区间 I = {I₁, I₂, ..., Iₙ}，其中每个区间 Iᵢ = [lᵢ, rᵢ] 是实轴上从左端点 lᵢ 到右端点 rᵢ 的一段。一个典型查询是：给定一个查询点 q，报告 I 中所有包含 q 的区间（即满足 lᵢ ≤ q ≤ rᵢ 的区间）。另一种查询是“区间重叠查询”：给定一个查询区间 Q = [a, b]，报告 I 中所有与 Q 有交集的区间（即满足 rᵢ ≥ a 且 lᵢ ≤ b 的区间）。

一个朴素的方法是遍历所有区间，检查每个是否满足条件，这需要 O(n) 时间。区间树的目标是：用 O(n log n) 时间和空间预处理这组区间，使得每个查询在 O(log n + k) 时间内完成，其中 k 是实际报告的区间数量。这是一个最优的输出敏感算法。

第二步：一维区间树的核心思想——基于端点的划分

区间树是一种平衡二叉搜索树（通常是红黑树或AVL树），但其节点存储的信息比单纯的键值更丰富。其根本思想是：

  1. 将所有区间的所有端点（包括所有 lᵢ 和 rᵢ）收集起来，排序去重，得到一组有序的“分割点”。
  2. 这些分割点将整个实轴划分成若干个连续的“基本区间”或“单元区间”。
  3. 然而，区间树并不直接存储这些基本区间。相反，它选择一个分割点 x_mid 作为根节点，将所有区间分为三类：
    • 完全位于 x_mid 左侧的区间（rᵢ < x_mid）。
    • 包含（穿过）x_mid 的区间（lᵢ ≤ x_mid ≤ rᵢ）。
    • 完全位于 x_mid 右侧的区间（lᵢ > x_mid）。
  4. 对第一类和第三类区间，分别在左子树和右子树中递归构建子树。而“包含 x_mid 的区间”这个集合，则直接存储在根节点中。

第三步：节点数据结构与查询算法

一个区间树的节点 v 存储以下信息：

  • x_mid：该节点对应的分割点（通常是该节点子树中所有区间端点的中位数）。
  • I_mid：所有包含 x_mid 的区间集合。
  • left_child, right_child：指向左、右子树的指针。

关键优化在于如何存储 I_mid。仅仅存储为一个列表是不够的。为了提高查询效率，我们需要对 I_mid 进行两次排序：

  • 创建一个列表 L，将 I_mid 中的区间按其左端点升序排列。
  • 创建另一个列表 R，将 I_mid 中的区间按其右端点降序排列。

查询算法（点查询 q）：

  1. 从根节点开始。如果 q < x_mid：
    • 检查该节点的 I_mid 列表。因为 I_mid 中所有区间都包含 x_mid，而 q 在 x_mid 左边，所以一个区间要包含 q，其左端点必须满足 l ≤ q。我们利用按左端点排序的列表 L：从 L 的头部开始扫描，只要当前区间的左端点 l ≤ q，这个区间就包含 q（因为其右端点 r ≥ x_mid > q）。一旦遇到某个区间左端点 l > q，由于 L 是左端点升序排列，后面的区间左端点都更大，所以扫描可以停止。报告所有满足条件的区间。
    • 然后，递归查询左子树（因为所有右端点大于 q 且完全在右边的区间，也可能包含 q，但通过 x_mid 划分，它们会在更深层的节点被处理）。
  2. 如果 q > x_mid，则对称处理：利用按右端点降序排列的列表 R，扫描所有右端点 r ≥ q 的区间（因为其左端点 l ≤ x_mid < q），然后递归查询右子树。
  3. 如果 q = x_mid，那么 I_mid 中的所有区间都包含 q，可以直接全部报告。

第四步：时间与空间复杂度分析

  • 构建：选择中位数 x_mid 需要 O(n) 时间（通过线性时间的选择算法）。将区间分类到左、中、右三组需要 O(n) 时间。对 I_mid 的列表进行两次排序，总时间与该列表大小成线性关系（因为每个区间只会在一个节点被排序）。递归构建左、右子树。整个过程的总时间复杂度是 O(n log n)，因为每个区间在树中从根到叶的路径上最多被处理 O(log n) 次（每层分类一次）。空间复杂度为 O(n log n)，因为在递归的每一层，一个区间可能被复制到多个节点的排序列表中？不，这里需要澄清：在标准的区间树中，每个区间只存储在一个节点中，即它所属的那个最浅的、其 x_mid 被它包含的节点。因此，总存储空间是 O(n)。但更精确地说，存储排序列表的额外空间是 O(n)。然而，构建过程中产生的递归栈和临时数组，总构建空间可以是 O(n log n)，但最终数据结构本身占用 O(n) 空间。标准分析通常给出 O(n log n) 构建时间和 O(n) 存储空间。
  • 查询：在每一层，我们要么扫描 I_mid 的两个列表之一。由于列表是排序的，扫描是“输出敏感”的——我们只扫描直到第一个不满足条件的位置。因此，在每一层，处理 I_mid 的时间是 O(1 + k_v)，其中 k_v 是在该节点报告的区间数。将所有层的 k_v 加起来就是总报告数 k。递归深度是 O(log n)。所以总查询时间是 O(log n + k)。

第五步：扩展到二维区间树（线段查询与矩形查询）

一维区间树可以直接用来解决平面线段与垂直线相交的查询：将每条水平线段视为其 x 坐标轴上的一个区间 [l, r]，查询垂直线 x = q 就等价于查询包含点 q 的所有一维区间。但这只针对水平线段。

对于更一般的二维正交范围查询（查询轴对齐矩形内的所有点），或者报告与一个给定矩形相交的所有矩形，我们需要二维区间树。其思想是“分而治之+组合数据结构”：

  1. 首先，在 x 坐标维度上建立一棵主区间树。每个主树节点 v 存储一个 x_mid 和一组“跨越” x_mid 的矩形（即矩形的 x 区间包含 x_mid）。与一维情况不同，这些二维矩形在 x 维度上跨越 x_mid，但在 y 维度上各有其区间。
  2. 在节点 v，我们不再只是存储两个排序列表，而是存储一个关联数据结构。这个关联数据结构处理的是：给定一个查询矩形在 y 轴上的区间 [y_low, y_high]，快速报告 v 节点中所有在 y 维度上与该查询区间有交集的矩形。这本质上又是一个一维区间查询问题！因此，我们可以为每个主树节点 v 建立一棵辅助的一维区间树，但这次是在 y 坐标上，存储的是该节点所有矩形的 y 坐标区间。
  3. 查询时，我们在主树上递归，在每一层，如果查询矩形的 x 范围完全在 x_mid 的一侧，就递归查询那一侧的子树。如果查询矩形的 x 范围与 x_mid 相交，那么我们既需要查询左、右子树，也需要在当前的关联数据结构（y方向区间树）上进行一次一维区间查询，来报告所有跨越 x_mid 且在 y 方向与查询相交的矩形。

第六步：复杂度与变种

  • 二维区间树的预处理时间为 O(n log n)，空间为 O(n log n)（因为每个矩形在每一层它所属的节点都会被存储在其关联数据结构中，一共 O(log n) 层）。查询时间为 O(log² n + k)。这可以通过区间树+优先搜索树等更复杂的结构优化到 O(log n + k)，但实现更复杂。
  • 区间树是分层数据结构的典型代表，它展示了如何将高维问题通过分治降维，并在每一层用低维数据结构解决子问题。类似的思路也用于线段树、范围树和优先搜索树。
  • 区间树特别适合处理“区间重叠”和“区间包含”查询，是计算几何数据库、计算机图形学（窗口查询）、地理信息系统（GIS）和调度问题（时间区间重叠）中的基础工具。

总结来说，区间树通过巧妙地将区间按分割点分类，并在每个节点对跨越该点的区间进行有序存储，实现了对数时间内定位和输出敏感的报告，是高维区间查询问题的一种高效解决方案。

计算几何中的区间树（Interval Tree） 我们开始探索计算几何中一种用于高效处理区间查询的数据结构——区间树。它的核心问题是：给定平面上的一组 水平线段 （或更一般地，轴对齐的矩形在某一维上的投影），如何快速找出所有与一条给定垂直线相交的线段？或者，给定一组区间（一维线段），如何快速找出所有与一个给定点（或另一个给定区间）重叠的区间？区间树为解决此类问题提供了优雅的解决方案。 让我们一步步构建这个知识体系： 第一步：问题定义与直观思路 首先，将问题形式化。我们有一组 n 个区间 I = {I₁, I₂, ..., Iₙ} ，其中每个区间 Iᵢ = [ lᵢ, rᵢ] 是实轴上从左端点 lᵢ 到右端点 rᵢ 的一段。一个典型查询是：给定一个查询点 q ，报告 I 中所有包含 q 的区间（即满足 lᵢ ≤ q ≤ rᵢ 的区间）。另一种查询是“区间重叠查询”：给定一个查询区间 Q = [ a, b] ，报告 I 中所有与 Q 有交集的区间（即满足 rᵢ ≥ a 且 lᵢ ≤ b 的区间）。 一个朴素的方法是遍历所有区间，检查每个是否满足条件，这需要 O(n) 时间。区间树的目标是：用 O(n log n) 时间和空间预处理这组区间，使得每个查询在 O(log n + k) 时间内完成，其中 k 是实际报告的区间数量。这是一个最优的输出敏感算法。 第二步：一维区间树的核心思想——基于端点的划分 区间树是一种平衡二叉搜索树（通常是红黑树或AVL树），但其节点存储的信息比单纯的键值更丰富。其根本思想是： 将所有区间的 所有端点 （包括所有 lᵢ 和 rᵢ ）收集起来，排序去重，得到一组有序的“分割点”。 这些分割点将整个实轴划分成若干个连续的“基本区间”或“单元区间”。 然而，区间树并不直接存储这些基本区间。相反，它选择一个分割点 x_ mid 作为根节点，将 所有区间 分为三类： 完全位于 x_ mid 左侧的区间（ rᵢ < x_ mid ）。 包含（穿过） x_ mid 的区间（ lᵢ ≤ x_ mid ≤ rᵢ ）。 完全位于 x_ mid 右侧的区间（ lᵢ > x_ mid ）。 对第一类和第三类区间，分别在左子树和右子树中递归构建子树。而“包含 x_ mid 的区间”这个集合，则直接存储在根节点中。 第三步：节点数据结构与查询算法 一个区间树的节点 v 存储以下信息： x_ mid ：该节点对应的分割点（通常是该节点子树中所有区间端点的中位数）。 I_ mid ：所有 包含 x_ mid 的区间集合。 left_ child, right_ child ：指向左、右子树的指针。 关键优化在于如何存储 I_ mid 。仅仅存储为一个列表是不够的。为了提高查询效率，我们需要对 I_ mid 进行两次排序： 创建一个列表 L ，将 I_ mid 中的区间 按其左端点升序 排列。 创建另一个列表 R ，将 I_ mid 中的区间 按其右端点降序 排列。 查询算法（点查询 q）： 从根节点开始。如果 q < x_ mid ： 检查该节点的 I_ mid 列表。因为 I_ mid 中所有区间都包含 x_ mid ，而 q 在 x_ mid 左边，所以一个区间要包含 q ，其左端点必须满足 l ≤ q 。我们利用按左端点排序的列表 L ：从 L 的头部开始扫描，只要当前区间的左端点 l ≤ q ，这个区间就包含 q （因为其右端点 r ≥ x_ mid > q ）。一旦遇到某个区间左端点 l > q ，由于 L 是左端点升序排列，后面的区间左端点都更大，所以扫描可以停止。报告所有满足条件的区间。 然后，递归查询左子树（因为所有右端点大于 q 且完全在右边的区间，也可能包含 q ，但通过 x_ mid 划分，它们会在更深层的节点被处理）。 如果 q > x_ mid ，则对称处理：利用按右端点降序排列的列表 R ，扫描所有右端点 r ≥ q 的区间（因为其左端点 l ≤ x_ mid < q ），然后递归查询右子树。 如果 q = x_ mid ，那么 I_ mid 中的所有区间都包含 q ，可以直接全部报告。 第四步：时间与空间复杂度分析 构建 ：选择中位数 x_ mid 需要 O(n) 时间（通过线性时间的选择算法）。将区间分类到左、中、右三组需要 O(n) 时间。对 I_ mid 的列表进行两次排序，总时间与该列表大小成线性关系（因为每个区间只会在一个节点被排序）。递归构建左、右子树。整个过程的总时间复杂度是 O(n log n) ，因为每个区间在树中从根到叶的路径上最多被处理 O(log n) 次（每层分类一次）。空间复杂度为 O(n log n) ，因为在递归的每一层，一个区间可能被复制到多个节点的排序列表中？不，这里需要澄清：在标准的区间树中，每个区间 只存储在一个节点中 ，即它所属的那个最浅的、其 x_ mid 被它包含的节点。因此，总存储空间是 O(n) 。但更精确地说，存储排序列表的额外空间是 O(n) 。然而，构建过程中产生的递归栈和临时数组，总构建空间可以是 O(n log n) ，但最终数据结构本身占用 O(n) 空间。标准分析通常给出 O(n log n) 构建时间和 O(n) 存储空间。 查询 ：在每一层，我们要么扫描 I_ mid 的两个列表之一。由于列表是排序的，扫描是“输出敏感”的——我们只扫描直到第一个不满足条件的位置。因此，在每一层，处理 I_ mid 的时间是 O(1 + k_ v) ，其中 k_ v 是在该节点报告的区间数。将所有层的 k_ v 加起来就是总报告数 k 。递归深度是 O(log n) 。所以总查询时间是 O(log n + k) 。 第五步：扩展到二维区间树（线段查询与矩形查询） 一维区间树可以直接用来解决平面线段与垂直线相交的查询：将每条水平线段视为其 x 坐标轴上的一个区间 [ l, r] ，查询垂直线 x = q 就等价于查询包含点 q 的所有一维区间。但这只针对水平线段。 对于更一般的二维正交范围查询（查询轴对齐矩形内的所有点），或者报告与一个给定矩形相交的所有矩形，我们需要 二维区间树 。其思想是“分而治之+组合数据结构”： 首先，在 x 坐标维度上建立一棵 主区间树 。每个主树节点 v 存储一个 x_ mid 和一组“跨越” x_ mid 的矩形（即矩形的 x 区间包含 x_ mid ）。与一维情况不同，这些二维矩形在 x 维度上跨越 x_ mid ，但在 y 维度上各有其区间。 在节点 v ，我们不再只是存储两个排序列表，而是存储一个 关联数据结构 。这个关联数据结构处理的是：给定一个查询矩形在 y 轴上的区间 [ y_ low, y_ high] ，快速报告 v 节点中所有在 y 维度上与该查询区间有交集的矩形。这本质上又是一个一维区间查询问题！因此，我们可以为每个主树节点 v 建立一棵 辅助的一维区间树 ，但这次是在 y 坐标上，存储的是该节点所有矩形的 y 坐标区间。 查询时，我们在主树上递归，在每一层，如果查询矩形的 x 范围完全在 x_ mid 的一侧，就递归查询那一侧的子树。如果查询矩形的 x 范围与 x_ mid 相交，那么我们既需要查询左、右子树，也需要在当前的关联数据结构（y方向区间树）上进行一次一维区间查询，来报告所有跨越 x_ mid 且在 y 方向与查询相交的矩形。 第六步：复杂度与变种 二维区间树的预处理时间为 O(n log n) ，空间为 O(n log n) （因为每个矩形在每一层它所属的节点都会被存储在其关联数据结构中，一共 O(log n) 层）。查询时间为 O(log² n + k) 。这可以通过 区间树+优先搜索树 等更复杂的结构优化到 O(log n + k) ，但实现更复杂。 区间树是 分层数据结构 的典型代表，它展示了如何将高维问题通过分治降维，并在每一层用低维数据结构解决子问题。类似的思路也用于 线段树 、 范围树 和 优先搜索树 。 区间树特别适合处理“区间重叠”和“区间包含”查询，是计算几何数据库、计算机图形学（窗口查询）、地理信息系统（GIS）和调度问题（时间区间重叠）中的基础工具。 总结来说，区间树通过巧妙地将区间按分割点分类，并在每个节点对跨越该点的区间进行有序存储，实现了对数时间内定位和输出敏感的报告，是高维区间查询问题的一种高效解决方案。