【算法】 二维前缀和
【C++】 二维数组、二维前缀和、scanf/printf
【难度】 普及−
n 行 m 列矩阵(n,m≤1000),k 次询问(k≤2×105),每次给左上角 (x1,y1) 和右下角 (x2,y2),求子矩阵和。元素范围 −1000∼1000。
矩阵最大 1000×1000,如果每次查询都遍历子矩阵求和,单次最坏 106 次运算,2×105 次查询直接爆炸。必须 O(1) 回答每次查询。
二维前缀和:预处理时 O(nm) 建表,查询时 O(1) 得出结果。
构建前缀和数组:
pre[i][j]=pre[i−1][j]+pre[i][j−1]−pre[i−1][j−1]+a[i][j]
查询 (x1,y1) 到 (x2,y2) 的子矩阵和:
sum=pre[x2][y2]−pre[x1−1][y2]−pre[x2][y1−1]+pre[x1−1][y1−1]
+------------------+
| (x1-1,y1-1) | (x1-1,y2)
| +---------+-----+
| | 子矩阵 | |
| (x2,y1-1)+-------+ (x2,y2)
| |
+------------------+
大矩形 = 上面矩形 + 左边矩形 - 左上角矩形 + 子矩阵和,移项即得子矩阵和。
2×2 矩阵:
构建前缀和:
- pre[1][1]=1
- pre[1][2]=pre[1][1]+pre[0][2]−pre[0][1]+2=1+0−0+2=3
- pre[2][1]=pre[1][1]+pre[2][0]−pre[1][0]+3=1+0−0+3=4
- pre[2][2]=pre[1][2]+pre[2][1]−pre[1][1]+4=3+4−1+4=10
查询 (1,1) 到 (2,2):
sum=pre[2][2]−pre[0][2]−pre[2][0]+pre[0][0]=10−0−0+0=10✓
查询 (1,2) 到 (2,2):
sum=pre[2][2]−pre[0][2]−pre[2][1]+pre[0][1]=10−0−4+0=6(2+4=6)✓
k 高达 2×105,必须用 scanf / printf,否则 cin / cout 可能超时。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int pre[N][N];
int main() {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int x;
scanf("%d", &x);
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + x;
}
}
while (k--) {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int ans = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1];
printf("%d\n", ans);
}
return 0;
}
- 时间复杂度:O(nm+k)。构建前缀和 106 次运算,2×105 次查询每次 O(1),总计约 1.2×106,非常安全。
- 空间复杂度:O(nm)。1005×1005 的
int 数组约 4 MB。
- 二维前缀和公式中的加减号容易搞混。记忆方法:大矩形减去上面和左边两个矩形,加回被多减的左上角矩形。
- 输入元素可能有负数,
pre 数组用 int 即可(最坏情况 1000×1000×(−1000)=−109,在 int 范围内)。 - 如果使用
cin / cout,记得加 ios::sync_with_stdio(false); 并避免混用 scanf / printf。
一维前缀和:pre[i]=pre[i−1]+a[i],查询 [l,r]=pre[r]−pre[l−1]。
二维前缀和是其自然扩展,核心思想都是预处理后用加减拼出答案。
- 激光炸弹:二维前缀和 + 固定窗口枚举
- 最大加权矩形:枚举边界 + 一维前缀和 + 最大子段和