题解 | 【模板】二维前缀和

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m, q;
    cin >> n >> m >> q;

    // 定义原始矩阵和二维前缀和矩阵（多开一行一列，便于处理边界）
    vector<vector<long long>> a(n + 1, vector<long long>(m + 1));
    vector<vector<long long>> sum(n + 1, vector<long long>(m + 1));

    // 输入原始矩阵（注意从 1 开始）
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];

    // 构建前缀和
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];

    // 每次查询使用前缀和计算
    while (q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        long long ans = sum[x2][y2] - sum[x1 - 1][y2]
                        - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
        cout << ans << '\n';
    }

    return 0;
}