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

// #牛客春招刷题训练营# + 链接

红色圈圈的前缀和 = 红色区域的总和 = 两个蓝色区域的前缀和之和 - 绿色区域的前缀和（重复部分）

a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + x;

计算区域和红色 = 蓝色的和 - 绿色的和

a[xx][yy] - a[x - 1][yy] - a[xx][y - 1] + a[x - 1][y - 1]

#include <array>
#include <iostream>
using namespace std;
array<array<long long, 1010>, 1010> a{0};
int main() {
  int n, m, p, x;
  cin >> n >> m >> p;
  for (int i = 1; i < n + 1; i++)
    for (int j = 1; j < m + 1; j++){
      cin >> x;
      a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + x;
    }
  int y, xx, yy;
  while(p--){
    cin >> x >> y >> xx >> yy;
    cout << a[xx][yy] - a[x - 1][yy] - a[xx][y - 1] + a[x - 1][y - 1] << endl;
  }
}
// 64 位输出请用 printf("%lld")