二维前缀和详解:从模板到激光炸弹实战
二维前缀和是处理矩阵区间查询的高效技巧。通过预处理,可以将任意子矩阵的和查询时间复杂度从 O(N*M) 降低到 O(1)。下面结合核心公式与两道经典题目进行实战讲解。
核心原理
构建前缀和矩阵
设原矩阵为 a[i][j],前缀和矩阵为 f[i][j]。f[i][j] 表示以 (1, 1) 为左上角,(i, j) 为右下角的矩形区域内所有元素的和。
状态转移方程如下:
f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j];
这里减去 f[i - 1][j - 1] 是因为它在加 f[i - 1][j] 和 f[i][j - 1] 时被重复计算了一次。注意数组下标通常从 1 开始,方便处理边界情况。
查询子矩阵和
若要查询以 (x1, y1) 为左上角,(x2, y2) 为右下角的子矩阵和,利用容斥原理可得:
sum = f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1];
这个操作的时间复杂度仅为 O(1),非常适合多次查询的场景。
实战演练
题目一:二维前缀和模板
这是一道直接考察前缀和构建与查询的基础题。输入一个 n*m 的矩阵,随后进行 q 次查询,每次给出一个子矩阵的坐标范围,输出该范围内的元素总和。
实现要点:
- 使用长整型防止求和溢出。
- 输入时直接累加到前缀和数组中,无需额外存储原矩阵。
- 查询时严格遵循上述公式。
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1010;
LL f[N][N];
int main() {
int n, m, q;
cin >> n >> m >> q;
// 构建前缀和
for(int i = ; i <= n; i++){
( j = ; j <= m; j++){
LL x;
cin >> x;
f[i][j] = f[i - ][j] + f[i][j - ] - f[i - ][j - ] + x;
}
}
(q--){
x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << f[x2][y2] - f[x1 - ][y2] - f[x2][y1 - ] + f[x1 - ][y1 - ] << endl;
}
;
}


