线段树在二维平面查询问题中的应用
字数 2394 2025-12-08 04:28:08

线段树在二维平面查询问题中的应用

题目描述
在二维平面上有 \(n\) 个点，每个点具有坐标 \((x_i, y_i)\) 和一个权重 \(w_i\)。要求高效处理两类查询：

  1. 更新操作：将某个点的权重修改为新值。
  2. 区域查询：查询一个矩形区域 \([x_{\min}, x_{\max}] \times [y_{\min}, y_{\max}]\) 内所有权重之和（或最大值、最小值等聚合信息）。
    其中 \(n\) 可能很大（例如 \(n \leq 10^5\)），需要支持多次操作（例如 \(m \leq 10^5\)）。

解题思路
一维线段树可以高效处理区间查询，但二维问题需要扩展。常见方法有：

  1. 二维线段树：用外层线段树维护 \(x\) 轴区间，每个节点存储一棵内层线段树（维护 \(y\) 轴区间）。
  2. 树套树：本质是两层线段树嵌套，但内存占用大，且代码复杂。
  3. 离线方法：结合扫描线思想，但需所有查询已知。

这里我们讲解二维线段树的实现。

详细步骤

步骤1：理解数据结构框架

  • 外层线段树：对 \(x\) 坐标区间进行划分。假设 \(x\) 坐标已离散化（因为实际坐标可能稀疏）。
  • 每个外层节点对应一个 \(x\) 区间 \([x_l, x_r]\)，它存储一个内层线段树，这个内层线段树管理所有 \(x\) 坐标落在 \([x_l, x_r]\) 内的点，但以 \(y\) 坐标为键。
  • 内层线段树同样需离散化 \(y\) 坐标。

关键：每个点会被外层线段树的 \(O(\log n)\) 个节点包含（因为每个点属于外层树从根到叶的路径上的每个节点），所以更新时需要更新所有这些节点的内层树。

步骤2：坐标离散化

  1. 收集所有点的 \(x\) 坐标，排序去重，得到数组 \(X\)，长度 \(lenX\)。
  2. 同样收集所有点的 \(y\) 坐标，排序去重，得到数组 \(Y\)，长度 \(lenY\)。
  3. 对任意点 \((x_i, y_i)\)，将其映射为离散化后的索引：
    • \(x\_id = \text{lower\_bound}(X, x_i)\)
    • \(y\_id = \text{lower\_bound}(Y, y_i)\)
      后续操作基于离散索引进行。

步骤3：构建二维线段树

  1. 外层线段树大小为 \(4 \times lenX\)（通常开四倍空间）。
  2. 每个外层节点 node_x 存储：
    • 一个内层线段树（大小为 \(4 \times lenY\) 的数组）
    • 或为了节省内存，用指针动态创建内层树。
  3. 内层线段树支持：
    • 单点更新：在 \(y\) 索引位置增加某个值。
    • 区间查询：查询 \(y\) 区间 \([y_l, y_r]\) 的和。

构建时，可以插入所有初始点：对每个点，在外层线段树中，对所有包含其 \(x\) 索引的外层节点，更新其内层树的对应 \(y\) 索引位置加上该点权重。

步骤4：更新操作
输入：点 \((x, y)\) 的新权重 \(new\_w\)，旧权重 \(old\_w\)（已知）。

  1. 计算 \(x, y\) 的离散索引 \(x\_id, y\_id\)。
  2. 在外层线段树中，从根节点开始递归，对每个包含 \(x\_id\) 的外层节点：
    • 找到其内层线段树，在位置 \(y\_id\) 上增加差值 \(new\_w - old\_w\)。
  3. 递归直到叶节点。
  4. 时间复杂度：外层树深度 \(O(\log lenX)\)，每个节点内层更新 \(O(\log lenY)\)，总 \(O(\log n \cdot \log m)\)（这里 \(n, m\) 是离散化后长度）。

步骤5：矩形区域查询
输入：矩形 \((x_1, x_2, y_1, y_2)\)（离散化后索引）。

  1. 在外层线段树查询 \(x\) 区间 \([x_1, x_2]\)，得到一组不相交的外层节点集合 \(nodes\)（标准线段树区间分解）。
  2. 对每个外层节点 \(node_x\)：
    • 取其内层线段树，查询 \(y\) 区间 \([y_1, y_2]\) 的区间和。
  3. 将所有节点的内层查询结果累加，即为矩形内权重和。
  4. 同样时间复杂度 \(O(\log n \cdot \log m)\)。

步骤6：内存优化

  • 如果所有点事先已知，可采用静态二维线段树，内层树用数组存储。
  • 如果点动态添加，可用动态开点的内层线段树，每个外层节点只创建用到的内层节点。

步骤7：示例操作流程
假设点集：
\(P_1(1,3,w=2), P_2(2,5,w=3), P_3(4,1,w=1)\)
离散化后：
\(X = [1,2,4]\)，索引 0,1,2
\(Y = [1,3,5]\)，索引 0,1,2

  1. 构建：对 \(P_1(1,3)\)，外层的 \(x\) 索引 0 属于多个外层节点，在每个节点的内层树的 \(y\) 索引 1 加 2。

  2. 查询矩形 \((x=1..2, y=2..5)\)：

    • 外层分解 \([0,1]\) 节点。
    • 内层查询 \(y\) 索引对应 [1,2] 区间，求和。

步骤8：适用场景与变体

  • 支持二维区域求和、最值、计数等。
  • 扩展到更高维（如三维线段树）则复杂度 \(O(\log^d n)\)。
  • 可用树状数组套树状数组（二维树状数组）简化实现，但只支持前缀矩形查询，可通过容斥转化为任意矩形。

总结
二维线段树是树套树的典型应用，将二维区间查询转化为两层一维查询，每次操作 \(O(\log^2 n)\)，适合平面点集动态区域查询问题。实现时需注意离散化、内存管理，并理解“每个点在外层树有 \(O(\log n)\) 个副本”这一特性。

线段树在二维平面查询问题中的应用 题目描述 在二维平面上有 \(n\) 个点，每个点具有坐标 \((x_ i, y_ i)\) 和一个权重 \(w_ i\)。要求高效处理两类查询： 更新操作 ：将某个点的权重修改为新值。 区域查询 ：查询一个矩形区域 \([ x_ {\min}, x_ {\max}] \times [ y_ {\min}, y_ {\max} ]\) 内所有权重之和（或最大值、最小值等聚合信息）。 其中 \(n\) 可能很大（例如 \(n \leq 10^5\)），需要支持多次操作（例如 \(m \leq 10^5\)）。 解题思路 一维线段树可以高效处理区间查询，但二维问题需要扩展。常见方法有： 二维线段树 ：用外层线段树维护 \(x\) 轴区间，每个节点存储一棵内层线段树（维护 \(y\) 轴区间）。 树套树 ：本质是两层线段树嵌套，但内存占用大，且代码复杂。 离线方法 ：结合扫描线思想，但需所有查询已知。 这里我们讲解 二维线段树 的实现。 详细步骤 步骤1：理解数据结构框架 外层线段树：对 \(x\) 坐标区间进行划分。假设 \(x\) 坐标已离散化（因为实际坐标可能稀疏）。 每个外层节点对应一个 \(x\) 区间 \([ x_ l, x_ r]\)，它存储一个 内层线段树 ，这个内层线段树管理所有 \(x\) 坐标落在 \([ x_ l, x_ r ]\) 内的点，但以 \(y\) 坐标为键。 内层线段树同样需离散化 \(y\) 坐标。 关键 ：每个点会被外层线段树的 \(O(\log n)\) 个节点包含（因为每个点属于外层树从根到叶的路径上的每个节点），所以更新时需要更新所有这些节点的内层树。 步骤2：坐标离散化 收集所有点的 \(x\) 坐标，排序去重，得到数组 \(X\)，长度 \(lenX\)。 同样收集所有点的 \(y\) 坐标，排序去重，得到数组 \(Y\)，长度 \(lenY\)。 对任意点 \((x_ i, y_ i)\)，将其映射为离散化后的索引： \(x\_id = \text{lower\_bound}(X, x_ i)\) \(y\_id = \text{lower\_bound}(Y, y_ i)\) 后续操作基于离散索引进行。 步骤3：构建二维线段树 外层线段树大小为 \(4 \times lenX\)（通常开四倍空间）。 每个外层节点 node_x 存储： 一个内层线段树（大小为 \(4 \times lenY\) 的数组） 或为了节省内存，用指针动态创建内层树。 内层线段树支持： 单点更新：在 \(y\) 索引位置增加某个值。 区间查询：查询 \(y\) 区间 \([ y_ l, y_ r ]\) 的和。 构建时，可以插入所有初始点：对每个点，在外层线段树中，对所有包含其 \(x\) 索引的外层节点，更新其内层树的对应 \(y\) 索引位置加上该点权重。 步骤4：更新操作 输入：点 \((x, y)\) 的新权重 \(new\_w\)，旧权重 \(old\_w\)（已知）。 计算 \(x, y\) 的离散索引 \(x\_id, y\_id\)。 在外层线段树中，从根节点开始递归，对每个包含 \(x\_id\) 的外层节点： 找到其内层线段树，在位置 \(y\_id\) 上增加差值 \(new\_w - old\_w\)。 递归直到叶节点。 时间复杂度：外层树深度 \(O(\log lenX)\)，每个节点内层更新 \(O(\log lenY)\)，总 \(O(\log n \cdot \log m)\)（这里 \(n, m\) 是离散化后长度）。 步骤5：矩形区域查询 输入：矩形 \((x_ 1, x_ 2, y_ 1, y_ 2)\)（离散化后索引）。 在外层线段树查询 \(x\) 区间 \([ x_ 1, x_ 2 ]\)，得到一组不相交的外层节点集合 \(nodes\)（标准线段树区间分解）。 对每个外层节点 \(node_ x\)： 取其内层线段树，查询 \(y\) 区间 \([ y_ 1, y_ 2 ]\) 的区间和。 将所有节点的内层查询结果累加，即为矩形内权重和。 同样时间复杂度 \(O(\log n \cdot \log m)\)。 步骤6：内存优化 如果所有点事先已知，可采用 静态二维线段树 ，内层树用数组存储。 如果点动态添加，可用 动态开点 的内层线段树，每个外层节点只创建用到的内层节点。 步骤7：示例操作流程 假设点集： \(P_ 1(1,3,w=2), P_ 2(2,5,w=3), P_ 3(4,1,w=1)\) 离散化后： \(X = [ 1,2,4 ]\)，索引 0,1,2 \(Y = [ 1,3,5 ]\)，索引 0,1,2 构建：对 \(P_ 1(1,3)\)，外层的 \(x\) 索引 0 属于多个外层节点，在每个节点的内层树的 \(y\) 索引 1 加 2。 查询矩形 \((x=1..2, y=2..5)\)： 外层分解 \([ 0,1 ]\) 节点。 内层查询 \(y\) 索引对应 [ 1,2 ] 区间，求和。 步骤8：适用场景与变体 支持二维区域求和、最值、计数等。 扩展到更高维（如三维线段树）则复杂度 \(O(\log^d n)\)。 可用 树状数组套树状数组 （二维树状数组）简化实现，但只支持前缀矩形查询，可通过容斥转化为任意矩形。 总结 二维线段树是 树套树 的典型应用，将二维区间查询转化为两层一维查询，每次操作 \(O(\log^2 n)\)，适合平面点集动态区域查询问题。实现时需注意离散化、内存管理，并理解“每个点在外层树有 \(O(\log n)\) 个副本”这一特性。