把 5.1 节"一段区间求和"的思路搬到二维网格上——任意一块矩形区域的和，也能 O(1) 查出来。
5.1 节解决的是"一维数组里，第 L 个到第 R 个数的和"。如果数据变成了二维网格（比如一张表格、一块棋盘），问题也升级成了"某一块矩形区域里所有数的和"——比如查一个班级座位表里"第 2 到 3 排、第 2 到 3 列的学生成绩总和"。思路完全一样：提前花一次力气把"前缀和"准备好，之后任意一块矩形区域的和，都能几步算出来，不需要重新挨个累加。
定义 prefix[i][j] 表示：从网格的左上角到第 i 行第 j 列这一块矩形区域里，所有数的总和。要推出 prefix[i][j]，可以利用已经算好的三块更小的区域，而不需要重新挨个加一遍。
arr[i][j] 本身没被包含进 B 或 C）。但 B 和 C 在左上角重叠了一块（橙色区域 A），直接加起来会把这块重叠区域多算一次，所以要减掉一次重叠部分，再把缺的那个新格子加上，正好凑出完整的目标区域。| 1 | int grid[n + 1][m + 1]; // 原网格，1-indexed |
| 2 | int prefix[n + 1][m + 1] = {0}; |
| 3 | |
| 4 | for (int i = 1; i <= n; i++) |
| 5 | for (int j = 1; j <= m; j++) |
| 6 | prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] |
| 7 | - prefix[i-1][j-1] + grid[i][j]; |
| 区域 | 含义 | 数值 |
|---|---|---|
| prefix[2][3] | 正上方区域（B） | 24 |
| prefix[3][2] | 正左方区域（C） | 24 |
| prefix[2][2] | 重叠区域（A，要减掉） | -14 |
| grid[3][3] | 新加入的格子本身 | +2 |
| prefix[3][3] = 24 + 24 - 14 + 2 | 36 | |
有了完整的 prefix 数组，查询任意矩形区域（左上角 (r1,c1)，右下角 (r2,c2)）的和，用的是同一套"加加减减"的思路，只是反过来用：先取一个包含目标区域的大矩形，再把多余的部分减掉。
prefix[3][3]，包含了目标区域和 D、E、F 全部），减去正上方多出来的 E，再减去正左方多出来的 F——但 D 这个角块同时属于 E 和 F，被减了两次，所以要把 D 单独加回来一次，结果正好只剩下目标区域。| 1 | int RangeSum2D(int prefix[][M], int r1, int c1, int r2, int c2) |
| 2 | { |
| 3 | return prefix[r2][c2] |
| 4 | - prefix[r1 - 1][c2] |
| 5 | - prefix[r2][c1 - 1] |
| 6 | + prefix[r1 - 1][c1 - 1]; |
| 7 | } |
| 项 | 数值 |
|---|---|
| prefix[3][3]（大矩形） | 36 |
| − prefix[1][3]（减正上方） | − 6 |
| − prefix[3][1]（减正左方） | − 15 |
| + prefix[1][1]（角块加回来） | + 1 |
| 结果 | 16 |
36 − 6 − 15 + 1 = 16——直接把这块区域的 4 个数（6,7,1,2）相加，结果也是 16，完全一致。不管目标矩形有多大，查询永远只需要这 4 次数组访问，时间复杂度是 O(1)。假设网格大小是 100×100，一共要回答 1000 次矩形区域查询（每次区域平均覆盖一半的网格）：
50×50=2500 个格子）估算，1000 次查询总共约 250万 次加法；二维前缀和只需要 O(n×m)=10000 次构建一次，之后每次查询只要 4 次数组访问，总共约 1万 次——快了 250 倍。| 做法 | 预处理 | 单次查询 |
|---|---|---|
| 每次直接累加 | 无 | O(区域大小) |
| 二维前缀和 | O(n × m) | O(1) |