【C++习题】26.前缀和_二维前缀和

文章目录

• • 题目链接：
  • 题目描述：
  • 解法
  • C++ 算法代码：

题目链接：

二维前缀和

题目描述：

解法

前缀和

1. 预处理一个前缀和矩阵

   dp[i,j]：表示从[1,1]到[i,j]位置，这段区间里面所有元素的和

   dp[i,j]：A+B+C+D = (A+B)+(A+C)+D-A = dp[i-1,j] + dp[i,j-1] + arr[i,j] - dp[i-1,j-1]

   A：(i-1)*(j-1) = dp[i-1,j-1]

   A+B：(i-1)*j = dp[i-1,j]

   A+C：(j-1)*i = dp[i,j-1]

   D：i*j = arr[i,j]

2. 使用前缀和矩阵

[x1,y1]~[x2,y2]

= D

= (A+B+C+D)-(A+B)-(A+C)+A

= dp[x2,y2]-dp[x1-1,y2]-dp[x2,y1-1]+dp[x1-1,y1-1]

C++ 算法代码：

#include <iostream>
using namespace std;
const int N = 1010;
int arr[N][N];
long long dp[N][N];
int n, m, q;
int main() {
    cin >> n >> m >> q;
	// 读入数据
    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] + arr[i][j] - dp[i - 1][j - 1];
	// 使用前缀和矩阵
    int x1, y1, x2, y2;
    while (q--) {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
    }
}