将一维前缀和拓展到多维的情形，就是多维前缀和。常见的多维前缀和的求解方法有两种。

第一种，基于容斥原理

输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含x1y1x2y2四个整数，代表一个子矩阵的坐上坐标和右下坐标。

对于每个询问，输出子矩阵中所有数的和。

输入格式

第一行，输入三个整数nmq

接下来输入n行，每行m个整数

接下来输入q行，每行四个整数，x1，y1，x2，y2，表示一组询问。

输出格式

共q行，每行输出一个询问的结果。

#include <bits/stdc++.h> 
using namespace std;
const int maxn = 1010;
int a[maxn][maxn];
int s[maxn][maxn];

int main(){
    int n,m,q;
    cin>>n>>m>>q;
    memset(s,0,sizeof(s)) ;
    //输入整数矩阵
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=m;++j){
            cin >> a[i][j];
        }
    }
    //预处理，把二维数组s[i][j]填满 
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            s[i][j] 
            = s[i-1][j]
            + s[i][j-1]
            - s[i-1][j-1]
            + a[i][j];
        }
    }

    while(q--) {
        int x1,y1,x2,y2;
        int sum = 0;
        cin >> x1 >> y1 >> x2 >> y2;
        sum 
        = s[x2][y2] 
        - s[x2][y1-1]
        - s[x1-1][y2]
        + s[x1-1][y1-1];
        cout << sum << endl; 
    }

}