题目描述

Point:
两个公式

1、预处理公式
$$s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1]$$

2、求值公式
$$\sum_{i = x_1}^{x_2}\sum_{j = y_1}^{y_2} a[x_2][y_2] = s[x_2][y_2] - s[x_1 - 1][y_2] - s[x_2][y_1 - 1] + s[x_1 - 1][y_1 - 1]$$

C++ 代码

#include <iostream>
using namespace std;
#define int long long

const int N = 1010;
int a[N][N], s[N][N];
signed main()
{
    // 输入
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j)
        {
            scanf("%lld",&a[i][j]);
            s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + a[i][j];
        }
    // 输出
    while(q--)
    {
        int x1, y1, x2, y2;
        scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
        printf("%lld\n",s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]);
    }

    return 0;
}