二维前缀和

全部数据点击查看

代码

#include <iostream>
#include <cstdio>
using namespace std;
long long a[1005][1005];
long long f[1005][1005];
int main() {
    long long n, m, k;
    cin >> n >> m >> k;
    for (long long i = 1; i <= n; ++i) {
        for (long long j = 1; j <= m; ++j) {
            cin >> a[i][j];
            f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j];
        }
    }
    for (long long i = 1; i <= k; ++i) {
        long long x1, x2, y1, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        cout << f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1] << '\n';
    }
    return 0;
}