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

#include <iostream>
#include <vector>
using namespace std;

//dp[i][j]表示从【1，1】的位置到【i，j】位置，这段区间里面所有元素的和
//dp[i][j]=dp[i-1]dp[j]+dp[j-1][i]+arr[i][j]-dp[i-1][j-1]

int main() {
    //1.读入数据
    int n=0,m=0,q=0;
    cin >> n >> m >> q;
    vector<vector<int>> arr(n+1,vector<int>(m+1));
    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));
    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;
    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;

    }
    return 0;

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