AcWing 796. 子矩阵的和
原题链接
简单
作者:
王小强
,
2021-02-11 14:52:57
,
所有人可见
,
阅读 252
二维前缀和 (你也可以说它是动态规化)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int m, n, q, x1, y1, x2, y2;
// debug helper function
void print(vector<vector<int>>& matrix) {
// corner case
if (matrix.empty()) return;
const int m = matrix.size(), n = matrix[0].size();
for (int y = 0; y < m; ++y) {
for (int x = 0; x < n; ++x) printf("%5d", matrix[y][x]);
printf("\n");
}
}
int sumRegion(vector<vector<int>>& dp, int x1, int y1, int x2, int y2) {
return dp[x2][y2]
- dp[x2][y1 -1]
- dp[x1 - 1][y2]
+ dp[x1 - 1][y1 - 1];
}
int main(void) {
cin >> m >> n >> q;
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int y = 1; y <= m; ++y)
for (int x = 1; x <= n; ++x) {
int t;
cin >> t;
dp[y][x] = t
+ dp[y][x - 1]
+ dp[y - 1][x]
- dp[y - 1][x - 1];
}
while (q--) {
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
printf("%d\n", sumRegion(dp, x1, y1, x2, y2));
}
}