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

import sys
import sys

input = sys.stdin.read
data = input().split()
idx = 0


n = int(data[idx])
m = int(data[idx + 1])
q = int(data[idx + 2])
idx += 3

arr = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        arr[i][j] = int(data[idx])
        idx += 1

pre = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    row_sum = 0
    for j in range(1, m + 1):
        # 前缀和：pre[i][j] = 上 + 左 - 左上 + 当前元素
        pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + arr[i][j]

res = []
for _ in range(q):
    x1 = int(data[idx])
    y1 = int(data[idx + 1])
    x2 = int(data[idx + 2])
    y2 = int(data[idx + 3])
    idx += 4

    ans = pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1]
    res.append(str(ans))


print("\n".join(res))