问题分析

我们需要解决一个二维平面区间求和问题：

有 n 个基站分布在二维平面上，每个基站有坐标 (x, y) 和功率值 p

需要处理 m 次矩形区域查询，每次查询给定一个轴对齐的矩形，要求返回该矩形内所有基站的功率总和

数据规模可能很大：n, m 最大可达 10⁵，坐标范围在 [-2³¹, 2³¹)

---

核心挑战

坐标范围极大：传统的二维数组前缀和方法无法使用，因为坐标范围达到 2³²，无法开辟如此大的数组

数据规模大：O(n×m) 的暴力算法在最大数据规模下需要 10¹⁰ 次操作，显然会超时

需要高效查询：必须设计 O(log n) 或 O(log² n) 级别的查询算法

---

解决方案：离线处理 + 扫描线 + 树状数组

---

第一步：问题转化

将二维区间查询问题转化为一维区间查询问题：

将所有的操作（基站插入和区域查询）按 x 坐标 排序

使用扫描线从左到右处理这些操作

在 y 方向上使用树状数组维护当前 x 位置的所有基站的功率分布

---

第二步：坐标离散化

由于坐标范围太大但实际出现的坐标值有限，我们需要进行坐标压缩：

收集所有出现的 y 坐标值（包括基站的 y 坐标和查询矩形的 y 边界）

对这些 y 坐标排序去重

建立从原始坐标到压缩后索引的映射

这样就将稀疏的大范围坐标映射到了稠密的小范围索引，使得我们可以使用树状数组等数据结构。

---

第三步：操作拆分与排序

将问题中的两种实体统一处理：

基站操作：

类型：数据插入

参数：(x, y, p) - 在位置 (x, y) 插入功率值为 p 的基站

查询操作：

每个矩形查询 [x₁, x₂] × [y₁, y₂] 拆分为两个操作：

开始查询：在 x₁ 位置，记录当前 [y₁, y₂] 区间的和（作为负值）

结束查询：在 x₂+1 位置，记录当前 [y₁, y₂] 区间的和（作为正值）

排序规则：

首先按 x 坐标升序排列

x 坐标相同时，按操作类型排序：先处理插入操作，再处理查询操作

---

第四步：扫描线处理

从左到右扫描所有操作：

对于插入操作：

将基站插入到树状数组中：在对应的 y 位置加上功率值 p

对于查询操作：

查询类型为"开始查询"：从结果中减去当前 [y₁, y₂] 区间的和

查询类型为"结束查询"：向结果中加上当前 [y₁, y₂] 区间的和

这样设计的原理是：对于任意查询矩形 [x₁, x₂] × [y₁, y₂]，最终结果 = (x₂位置的和) - (x₁-1位置的和)

---

第五步：树状数组维护

在 y 方向上使用树状数组（Fenwick Tree） 来维护前缀和：

树状数组的优势：

空间复杂度：O(k)，其中 k 是离散化后的坐标数量

时间复杂度：单点更新和前缀查询都是 O(log k)

代码简洁，常数因子小

支持的操作：

update(pos, value)：在位置 pos 加上 value

query(pos)：查询 [1, pos] 的前缀和

range_query(l, r)：查询 [l, r] 的区间和，通过 query(r) - query(l-1) 实现

---

算法复杂度分析

时间复杂度

坐标离散化：O((n + m) log(n + m))

操作排序：O((n + m) log(n + m))

扫描线处理：O((n + m) log n)

总复杂度：O((n + m) log(n + m))，能够处理 10⁵ 级别的数据

空间复杂度

存储所有操作：O(n + m)

树状数组：O(n + m)

坐标映射：O(n + m)

总复杂度：O(n + m)

---

算法正确性证明

查询完整性

对于每个查询矩形 [x₁, x₂] × [y₁, y₂]：

在 x₁ 位置，我们记录当前已插入的所有 x < x₁ 的基站在 [y₁, y₂] 区间的和（记为 S₁）

在 x₂+1 位置，我们记录当前已插入的所有 x ≤ x₂ 的基站在 [y₁, y₂] 区间的和（记为 S₂）

最终结果 = S₂ - S₁，正好是 x ∈ [x₁, x₂] 且 y ∈ [y₁, y₂] 的所有基站功率和

边界处理

由于题目明确说明包含边界，我们的区间查询 [y₁, y₂] 直接包含两个端点

查询拆分时使用 x₂+1 而不是 x₂，确保包含 x = x₂ 的基站