二维前缀和是将原二维数组预处理为前缀和数组prefix，使任意子矩阵[r1,c1]到[r2,c2]的和可在O(1)时间内计算，公式为prefixr2−prefixr2−prefixr1−1+prefixr1−1，需以1为起始索引并多开一行一列以避免边界判断。
什么是二维前缀和，它为什么能加速区域求和
二维前缀和不是语法特性，而是用空间换时间的预处理技巧。它把原数组 matrix 转换成一个新数组 prefix，使得任意子矩阵 [r1, c1] 到 [r2, c2]（含端点）的和能在 O(1) 时间内算出。核心公式是：sum = prefix[r2][c2] - prefix[r2][c1-1] - prefix[r1-1][c2] + prefix[r1-1][c1-1]
前提是 prefix 的索引从 1 开始（即多开一行一列），避免边界判断。如果从 0 开始，每次都要写 if 检查，反而拖慢且易错。
如何构造二维前缀和数组（含边界处理）
构造时必须严格按顺序：先保证行方向累加，再列方向累加；或用递推式统一处理。推荐后者，更清晰且不易漏项：
for (int i = 1; i <p>注意三点：</p>
-
matrix[i-1][j-1]是因为prefix多开了一维，而原数组是 0-indexed - 所有
prefix行列都从 1 开始，第 0 行和第 0 列初始化为 0 - 不能交换
i和j循环顺序——虽然数学上等价，但若提前访问未计算的prefix[i][j-1]就会出错
怎么用前缀和快速查询矩形区域和（含坐标转换）
查询时输入通常是 0-indexed 的左上 (r1, c1) 和右下 (r2, c2)。必须先转成 1-indexed 坐标再套公式：
int getSum(int r1, int c1, int r2, int c2) {
// 转成 prefix 的 1-indexed 坐标
r1++; c1++; r2++; c2++;
return prefix[r2][c2]
- prefix[r2][c1-1]
- prefix[r1-1][c2]
+ prefix[r1-1][c1-1];
}
常见错误：
- 忘记加 1，直接用
r1当作prefix下标 → 访问越界或结果偏小 - 没确保
r1 ，函数应提前校验，否则公式失效 - 在多次查询场景中，反复构造
prefix—— 它只需建一次，后续所有查询都是O(1)
实际使用时要注意内存与初始化细节
二维前缀和真正生效的前提是内存布局合理、初始化干净。C++ 中推荐用 vector 或原生二维数组，但必须显式清零：
vector<vector>> prefix(m + 1, vector<int>(n + 1, 0));</int></vector>
别用 new int*[m+1] 手动分配——容易漏初始化第 0 行/列，导致减法出现随机大数。另外，如果原矩阵元素是 long long，prefix 也必须同类型，否则中间求和可能溢出。
最常被忽略的一点：当题目要求「动态更新单点值」时，二维前缀和完全不适用，得换二维树状数组或线段树——它只适合静态批量查询。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
