题目分析


给定一个 n 行 m 列的矩阵,以及若干次查询,每次查询给出两个坐标,要求计算这两个坐标所围成的子矩阵的元素之和。
暴力解法
直接模拟求和,每次询问的时间复杂度为 O(mn),总复杂度为 O(qm*n)。
前缀和优化
通过预处理前缀和矩阵,可以将单次查询的时间复杂度降低至 O(1)。
核心思想是利用容斥原理:目标区域面积 = 大矩形面积 - 多余部分面积。

使用前缀和公式计算任意子矩阵和:
Sum(x1, y1, x2, y2) = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]

代码实现
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 1. 读入数据
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> arr(n + 1, vector<int>(m + 1));
for ( i = ; i <= n; i++) {
( j = ; j <= m; j++) {
cin >> arr[i][j];
}
}
vector<vector< >> (n + , < >(m + ));
( i = ; i <= n; i++) {
( j = ; j <= m; j++) {
dp[i][j] = dp[i - ][j] + dp[i][j - ] - dp[i - ][j - ] + arr[i][j];
}
}
(q--) {
x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << dp[x2][y2] - dp[x1 - ][y2] - dp[x2][y1 - ] + dp[x1 - ][y1 - ] << endl;
}
;
}


