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

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

int main() {
    int n,m,q;
    cin>>n>>m>>q;
    vector<vector<long long>> matrix(n,vector<long long>(m,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>matrix[i][j];
        }
    }
    vector<vector<int>> search(q,vector(4,0));
    for(int i=0;i<q;i++){
        for(int j=0;j<4;j++){
            cin>>search[i][j];
        }
    }
    //先推到出以(0,0)到(x,y)的和矩阵prefix
    vector<vector<long long>> prefix(n+1,vector<long long>(m+1,0));
    for(int i=1;i<n+1;i++){
        for(int j=1;j<m+1;j++){
            prefix[i][j]=prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+matrix[i-1][j-1];
        }
    }
    for(int i=0;i<q;i++){
        int x1=search[i][0];
        int y1=search[i][1];
        int x2=search[i][2];
        int y2=search[i][3];
        cout<<(prefix[x2][y2]-prefix[x1-1][y2]-prefix[x2][y1-1]+prefix[x1-1][y1-1])<<endl;
    }
    return 0;
} 
// 64 位输出请用 printf("%lld")