本文共 930 字，大约阅读时间需要 3 分钟。

题目描述

算法思想

代码实现

#include 
   
      using namespace std;  const int N = 1010;  int a[N][N], s[N][N];  int main() {      int n, m, q;      cin >> n >> m >> q;      for(int i = 1; i <= n; i++) {          for(int j = 1; j <= m; j++) {              scanf("%d", &a[i][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;  }
   

这个算法通过预先计算矩阵的前缀和，使得每个子矩阵的和可以在常数时间内查询。这种预处理方法的时间复杂度为O(nm)，而每个查询的时间复杂度为O(1)，整体复杂度为O((n + m) + q)。