$$二维前缀和$$

$s[i][j]$ 表示的是 从 左上角 $(1, 1)$ 到 右下角 $(i, j)$ 这个大矩形的面积。

那么如何构建出来？

看上图，这里会用到动态规划的思想，当我们求到 $(i, j)$ 时所有横坐标小于 $i$，纵坐标小于 $j$ 的矩形的面积都已经算出来了，我们可以直接用。（作为新人你只需要理解我们按行从左到右枚举位置求 $s[i][j]$ 矩形面积，当我们枚举到 $(i, j)$ 时，之前枚举到的矩形面积已经全部算出来了，这个也是 $for$ 循环的逻辑）。按照这个思路，我么可以得出 蓝色部分 = 绿色 + 紫色 - 橙色 + $a[i][j]$，即 $s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];$，很显然 $s[i][j]$ 所用到的状态（等式右边两个 $s$）都是已经算出来过的（有值），可以直接用。

于是我们便得到二维前缀和预处理公式

$$s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; $$

下标从一开始并且将数组放全局（默认全 $0$），可以正确处理第一行第一列边界。

那如何计算给定矩形的面积呢？

显然为我们要求解的 绿色区域面积 = 蓝色 - 棕色 - 紫色 + 橙色。

于是我们便得到任意矩形面积公式

$$s = s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] $$

本题输入输出规模很大，cin, cout 会被卡

#include<iostream>

using namespace std;

const int N = 1010;
int s[N][N], a[N][N];
int n, m, q;

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

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
          scanf("%d", &a[i][j]);

     for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
          s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
  
    while (q--)
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }

    return 0;
}

本文图片引用自林小鹿