摘要
Title: 796. 子矩阵的和
Tag: 二维前缀和
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

796. 子矩阵的和

• 题意

  输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。
  对于每个询问输出子矩阵中所有数的和。

• 思路

  

  s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j] 求a数组的前缀和，公式中就只用加$a[i][j]$，其余都是新数组，即s数组

• 代码

  N = int(1e3 + 100)
  
  a = [[0] * N for _ in range(N)]
  s = [[0] * N for _ in range(N)] #前缀和数组
  
  n, m, q = map(int, input().split())
  
  for i in range(1, n + 1):
    a[i][1:] = list(map(int, input().split()))
  
  for i in range(1, n + 1):
    for j in range(1, m + 1):
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]
  
  for i in range(q):
    x1, y1, x2, y2 = map(int, input().split())
    print(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1])