刷题——【模板】二维前缀和

题目

描述
给你一个 n 行 m 列的矩阵 A ，下标从1开始。

接下来有 q 次查询，每次查询输入 4 个参数 x1 , y1 , x2 , y2

请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和，
输入描述：
第一行包含三个整数n,m,q.

接下来n行，每行m个整数，代表矩阵的元素

接下来q行，每行4个整数x1, y1, x2, y2，分别代表这次查询的参数

输出描述：
输出q行，每行表示查询结果。

题目链接

二维前缀和题目链接

题解

方法一

显而易见，最容易想到的方法就是先录入数据，然后一行一行的求和。但是这种方法会超时。其时间复杂度为O（m * n * q）。

#include <iostream>
#include <vector>using namespace std;int main() {int n, m, q;cin >> n >> m >> q;vector<vector<int>> matrix(n, vector<int>(m));for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> matrix[i][j];}}for (int i = 0; i < q; ++i) {int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;int sum = 0;for (int row = x1 - 1; row <= x2 - 1; ++row) { // 数组是从0开始的，所以要减1for (int col = y1 - 1; col <= y2 - 1; ++col) {sum += matrix[row][col];}}cout << sum << endl;}return 0;
}

不多赘述，下面看最优解。

方法二

一遍遍求显然复杂度太高，那么能不能先求取（1，1）到（x，y）的和在找规律求取题目要求的和呢？答案是可以的。

先求前缀和数组，显然我们不能每次都遍历一次求和，复杂度太高，那么就可以利用前面已经求出的值求出当前的和。

ps：因为下标从1开始，所以不用考虑越界。

由此可以得出D区域的求和公式为dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j];

再求某一个小区域的和，与此类似，画图总结公式，利用已知和求取。

由此可以得出D区域的求和公式为dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];

最终代码：

#include <iostream>
#include <vector>
using namespace std;int main() 
{int n, m, q;cin >> n >> m >> q;vector<vector<int>> arr(n+1,vector<int>(m+1));vector<vector<long long>> dp(n+1,vector<long long>(m+1));for (int i = 1; i <= n; i++) for(int j = 1; j <= m; j++)cin >> arr[i][j];for (int i = 1; i <= n; i++) for(int j = 1; j <= m; j++)dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j];int x1,y1, x2, y2;long long sum = 0;for (int i = 1; i <= q; i++) {cin >> x1 >> y1 >> x2 >> y2;sum = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];cout << sum << endl;}return 0;
}