题目描述
blablabla
样例
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n = 0, m = 0, q = 0;
cin >> n >> m >> q;
vector<vector<int>> mat (n, vector<int> (m, 0));
for (int row = 0; row < n; row ++) {
for (int col = 0; col < m; col ++) {
int num = 0;
scanf("%d", &num);
mat[row][col] = num;
}
}
// 计算2维前缀和
// preSum[i, j] 表示 0~i - 1行 0~j - 1列的和 (前i行 前j列)
vector<vector<int>> preSum (n + 1, vector<int> (m + 1, 0));
for (int row = 1; row < n + 1; row ++) {
for (int col = 1; col < m + 1; col ++) {
preSum[row][col] = preSum[row - 1][col] + preSum[row][col - 1] - preSum[row - 1][col - 1];
preSum[row][col] += mat[row - 1][col - 1];
}
}
// 查询
while (q --) {
int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
cin >> x1 >> y1 >> x2 >> y2;
cout << preSum[x2][y2] - preSum[x1 - 1][y2] - preSum[x2][y1 - 1] + preSum[x1 - 1][y1 - 1] << "\n";
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla