题解 | #【模板】二维前缀和#
【模板】二维前缀和
http://www.nowcoder.com/practice/99eb8040d116414ea3296467ce81cbbc
解题思路大佬们都说了，这里提供下Python实现过程，供大家参考
while True:
try:
n, m, q = map(int, input().split())
l = []
for _ in range(n):
l.append(list(map(int, input().split())))
# dp[i][j]表示起点到l[i-1][j-1]的子矩阵的和
dp = [[0 for i in range(m + 1)] for j in range(n + 1)] # 让dp坐标与x1,y1,x2,y2,对齐 并且添加两个辅助列
for i in range(1, n + 1): # 行
for j in range(1, m + 1): # 列
# 状态转移方程，dp[i][j]等于其上方所有行之和加上其左方所有列之和减去其左上方行列交叉导致的减掉双倍区域，再加上本单元格的值
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + l[i - 1][j - 1] - dp[i - 1][j - 1]
for k in range(q):
x1, y1, x2, y2 = map(int, input().split())
# (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和。x2,y2的值 减去 x1, y1上面的行左边的列，再加上重叠相减的部分
num = dp[x2][y2] + dp[x1 - 1][y1 - 1] - dp[x1 - 1][y2] - dp[x2][y1 - 1]
print(num)
except:
break
算法太卷啦
