思想概括及问题描述
子矩阵和问题的描述:给你一个二维矩阵,如何快速求出其中的子矩阵的和?
可以利用前缀和的思想,对于每一个坐标都求出一个到左上角原点的求和矩阵,然后利用推到出的公式即可求出子矩阵的和。
前缀和一般分为两步,就算是矩阵的前缀和也不例外:
- 推导前缀矩阵
- 利用公式对子区间进行求和
公式
前缀矩阵每一个坐标的推导公式(其中 q 是题目所给的未经过处理的原矩阵):
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + q[i][j]
子区间的查询公式(假如需要查询[x1][y1]-[x2][y2]这个矩阵区间的求和值):
Sum = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
原题链接和代码
#include <iostream>
using namespace std;
int m, n, q;
const int N = 10005, M = 1005;
// n 行
int arr[N][M];
// 原矩阵数组
int qrr[N][M];
// 处理后的查询数组
int main() {
// cin >> n >> m >> q;
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
scanf("%d", &arr[i][j]);
}// 输入原矩阵
}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
qrr[i][j] = qrr[i-1][j] + qrr[i][j-1] - qrr[i-1][j-1] + arr[i][j];
}// 得到处理后的前缀矩阵
}
while (q --) {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", qrr[x2][y2] - qrr[x1-1][y2] - qrr[x2][y1-1] + qrr[x1-1][y1-1]);
}
return 0;
}