01先把问题说具体
网格频繁查询任意矩形总和,逐格累加每次要 O(面积),怎样预处理后常数时间回答?
02一步步得到方法
多出一行一列不是浪费
定义 P[r][c] 为原网格 [0,r)×[0,c) 的和,P 的第 0 行、第 0 列全为零。构造当前格时,把上方和左方前缀相加,减去重复的左上交集,再加当前元素。
查询 [r1,r2)×[c1,c2) 时,从大前缀 P[r2][c2] 减去上方与左方;左上区域被减了两次,因此再加回来。画四个矩形比背符号更可靠。
适用范围与维护代价
预处理适合静态网格、多次查询。单点更新会影响右下方很多前缀值,不能直接宣称更新也为 O(1)。更新频繁时考虑二维树状数组或其他动态结构。
把四个前缀画成覆盖区域
先把查询矩形写成半开区间 [r1,r2)×[c1,c2)。P[r2][c2] 覆盖左上大矩形,减上方、减左方时左上角重叠区被减了两遍,所以要补回一次。每个小格的最终系数只有查询内为1、查询外为0。
多留一行和一列零,使贴着上边界或左边界的查询也能使用同一公式。它减少的不是渐近复杂度,而是边界分支和下标错误。
03把一个小例子完全算清楚
网格 [[1,2,3],[4,5,6]],查询行 [0,2)、列 [1,3)。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 第一行前缀 | [0,1,3,6] | 第 0 列补零 |
| 第二行前缀 | [0,5,12,21] | P[2][2]=3+5−1+5=12 |
| 查询 | 21−0−5+0=16 | 得到 2+3+5+6 |
窄屏可左右滑动表格,阅读完整计算与理由。
所有坐标采用半开区间,矩形宽高分别是 c2−c1、r2−r1。
04为什么这个方法成立
- 构造公式通过容斥使每个格子被计算一次。
- 查询中目标矩形系数为 1,上方和左方系数为 0。
- 左上重叠区域系数为 1−1−1+1=0,因此不会混入答案。
05把推导翻译成代码
Python · 可独立运行的教学实现
def build_prefix(grid):
rows = len(grid)
cols = len(grid[0]) if rows else 0
p = [[0]*(cols+1) for _ in range(rows+1)]
for r in range(rows):
for c in range(cols):
p[r+1][c+1] = grid[r][c] + p[r][c+1] + p[r+1][c] - p[r][c]
return p
def rectangle_sum(p, r1, c1, r2, c2):
return p[r2][c2] - p[r1][c2] - p[r2][c1] + p[r1][c1]逐个理解关键决定
p[r+1][c+1]- 原格 (r,c) 对应前缀终点 (r+1,c+1),不是同坐标。
+ p[r1][c1]- 补回被重复减去的交集。
06时间、空间与实现范围
R×C 网格预处理时间和空间 O(RC),每次合法矩形查询 O(1)。
本代码要求规则矩形网格且查询坐标有序、在范围内;空矩形自然返回 0。
07改变条件,检查哪里会出错
混用闭区间与半开区间
若输入题目给右下角闭坐标,应先把终点各加 1,再套公式。
把预处理后的表当作实时数据
原矩阵改变后前缀表不会自动更新;频繁修改应考虑二维树状数组等结构。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
查询单格 (1,1) 应传什么?
需要一点提示
终点不包含。
查看解析与答案
r1=1,c1=1,r2=2,c2=2,结果 5。
为什么只减上方和左方不行?
需要一点提示
画出两块的交集。
查看解析与答案
交集被重复减,必须加一次。
每天修改网格后仍用旧前缀查询可靠吗?
需要一点提示
索引依赖原始数据。
查看解析与答案
不可靠,要重建、增量维护所有受影响项,或换动态范围查询结构。