【题解】子矩阵的和

二维前缀和公式： s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
求给定子矩阵的值： 起点 x1、y1，终点x2、y2 的矩阵之和： sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010;

int n, m, k;
int a[N][N];
int s[N][N];

int main()
{
    cin >> n >> m >> k;
    
    //计算前缀可边读边算
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j<= m; j ++)
        {
            cin >> s[i][j];
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    
    //询问给定左上角坐标和右下角坐标的子矩阵之和
    while (k --)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << endl; 
    }
    
    return 0;
}