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

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

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];
        }
    }

    //2.预处理出来一个前缀和矩阵
    //由于数据的范围，在两数相加时可能会有溢出，所以我们这里使用long long类型数组
    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]-dp[i-1][j-1]+arr[i][j];
        }
    }

    //3.使用前缀和矩阵
    int x1=0,y1=0,x2=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;
    }

    return 0;
}