5. 前缀和与差分

5.1 子矩阵的和

初始化

(x1, x1) 到 (x2, y2) 区域

#include<iostream>
using namespace std;
const int n = 1010;
int N, M, K;
int a[n][n];
int main()
{
    cin >> N >> M >> K;
    for(int i = 1;i <= N;i ++ )
        for(int j = 1;j <= M;j ++)
            scanf("%d", &a[i][j]), a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + a[i][j];

    while(K--)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << a[x2][y2] - a[x1-1][y2] - a[x2][y1-1] + a[x1-1][y1-1] << endl;
    }


    return 0;
}