题解 | #【模板】二维前缀和#

对于该问题就是对于一个区间的面积来规划。

将整二维数组进行一个区域化，然后求（x1,y1）到(x2,y2)这一块的面积，也就是图中A的面积，但是对于图中的面积(x2,y2）如果使用就会增加难度。不如像一个固定的点位来进行一个整体面积的固定。

对于整体的面积S就是A+B+C+D=S；来表示如果需要求取D=S-(A+B)-(A+C)-A;这里不直接进行的那个模块的减去就是因为(x2,y2)是不固定的。 假如D的左上角是a(x1,y1),右下角b(x2,y2)。使用一个新的二维数组dp来存储面积，dp[i][j]就是以(i,j)位置结束的面积的大小（也就是每一个模块的右下角）。状态表示 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i ][j ]-dp[i-1][j-1] 对于B的右下角就是(x1-1,y2),C的右下角(x2,y1-1);就可以推断出一个状态转移方程 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() {
    int n = 0, m = 0, q = 0;
    cin >> n >> m >> q;
    vector<vector<int>> arr(n+1, vector<int> (m+1,0));
    for (int i = 1; i <=n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }

    vector<vector<long long >> dp(n + 1, vector<long long>(m + 1, 0));
    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=0,x2=0,y1=0,y2=0;
    for(int i=0;i<q;i++)
    {
       
        cin>>x1>>y1>>x2>>y2;
        cout<<dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]<<endl;
    }

}
// 64 位输出请用 printf("%lld")