专题进阶 · 数组技巧推荐总顺序 · 第 38 / 148 课

用半开坐标和容斥计算矩形和,避免重复减去重叠区域。

先学会这些,再进入本课 前缀和
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 数组技巧

二维前缀和2D Prefix Sum

用容斥计算矩形和:大矩形减上方、左方,再加回重叠部分。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

用半开坐标和容斥计算矩形和,避免重复减去重叠区域。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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. 构造公式通过容斥使每个格子被计算一次。
  2. 查询中目标矩形系数为 1,上方和左方系数为 0。
  3. 左上重叠区域系数为 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,1) 应传什么?

需要一点提示

终点不包含。

查看解析与答案

r1=1,c1=1,r2=2,c2=2,结果 5。

练习 2 · 边界与辨析

为什么只减上方和左方不行?

需要一点提示

画出两块的交集。

查看解析与答案

交集被重复减,必须加一次。

练习 3 · 变式与迁移

每天修改网格后仍用旧前缀查询可靠吗?

需要一点提示

索引依赖原始数据。

查看解析与答案

不可靠,要重建、增量维护所有受影响项,或换动态范围查询结构。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。