AcWing 796. 子矩阵的和

原题链接：https://www.acwing.com/activity/content/problem/content/830/

与前缀和大致相似，我们定义子矩阵数组preSum[]中，表示所有位于左下角的元素之和。如表示原数组中坐标和的元素和。

sub_matrix

于是，可以得出以下等式： 因此，代码如下：

#include <iostream>

#define N 1005
#define M 1005
#define Q 200005

int preSum[N][M];
int nums[N][M];
int ans[Q];

int n, m, q;

void build() {
    preSum[0][0] = 0;
    for (int i = 1; i < n; ++i) preSum[i][0] = 0;
    for (int i = 1; i < m; ++i) preSum[0][i] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + nums[i-1][j-1];
        }
    }
}

int getSum(int x, int y) {
    return preSum[x][y];
}


int main() {
    
    scanf("%d %d %d", &n, &m, &q);
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &nums[i][j]);
        }
    }
    
    build();
    
    int x1, y1, x2, y2;
    for (int i = 0; i < q; ++i) {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        ans[i] =  getSum(x2, y2) - getSum(x2, y1 -1) - getSum(x1 - 1, y2) + getSum(x1 - 1, y1 - 1);
    }
    
    for (int i = 0; i < q; ++i) {
        printf("%d\n", ans[i]);
    }
    
    return 0;
}