（蓝桥杯）二维数组前缀和典型例题——子矩阵求和
题目描述
小 A 同学有着很强的计算能力，张老师为了检验小 AA同学的计算能力，写了一个 n 行 m 列的矩阵数列。
张老师问了小 A 同学 k 个问题，每个问题会先告知小 A 同学 4 个数 x1,y1,x2,y2画出一个子矩阵，张老师请小 A同学计算出这个子矩阵中所有数的和。
请你编程帮助张老师计算出结果。
输入
第一行包含三个整数 n，m，k 。
接下来 n 行，每行包含 m 个整数。
接下来 k 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。
数据范围
1≤n,m≤1000。
1≤k≤200000。
1≤x1≤x2≤n,≤y1≤y2≤m。
矩阵内元素的值均在 [−1000,1000] 的范围内。
输出
共 k 行，每行输出一个询问的结果。
样例
输入：
3 5 4
1 1 6 7 4
6 10 4 9 9
2 6 7 3 7
1 2 2 4
2 4 3 5
2 2 3 5
1 3 2 4输出：
37
28
55
26
知识点
1.二维数组前缀和
2、python输入输出优化
问题： 这是第一版的代码 老是运行超时
解法：因为 Python 的
input()和print()在大量数据时可能会比较慢。我们可以使用sys.stdin.readline()来代替input()，并使用sys.stdout.write()来代替print()，以减少 I/O 操作的时间开销。输入优化：使用
sys.stdin.readline()代替input()，这样可以更快地读取输入数据。输出优化：使用
sys.stdout.write()代替print()，这样可以更快地输出结果。注意sys.stdout.write()不会自动添加换行符，所以需要手动添加\n。输入优化：使用
sys.stdin.readline()代替input()在 Python 中，
input()函数用于从标准输入读取一行数据，并返回一个字符串。虽然input()使用起来非常方便，但在处理大量输入数据时，它的性能可能会比较差。这是因为input()函数在内部进行了一些额外的处理，比如处理换行符、缓冲区管理等。
sys.stdin.readline()是一个更底层的输入函数，它直接从标准输入读取一行数据，并返回一个字符串，包括行尾的换行符。使用sys.stdin.readline()可以减少一些不必要的处理，从而提高输入的效率。示例
import sys # 使用 input() 读取一行数据 line = input().strip() # strip() 用于去除行尾的换行符 # 使用 sys.stdin.readline() 读取一行数据 line = sys.stdin.readline().strip() # 同样需要 strip() 去除行尾的换行符输出优化：使用
sys.stdout.write()代替print()
print()函数用于将数据输出到标准输出，并自动添加换行符。虽然print()使用起来非常方便，但在处理大量输出数据时，它的性能可能会比较差。这是因为print()函数在内部进行了一些额外的处理，比如格式化输出、换行符管理等。
sys.stdout.write()是一个更底层的输出函数，它直接将字符串写入标准输出，不会自动添加换行符。使用sys.stdout.write()可以减少一些不必要的处理，从而提高输出的效率。示例
import sys # 使用 print() 输出数据 print("Hello, World!") # 使用 sys.stdout.write() 输出数据 sys.stdout.write("Hello, World!\n") # 需要手动添加换行符性能对比
在处理大量数据时，使用
sys.stdin.readline()和sys.stdout.write()可以显著提高程序的运行效率。以下是一个简单的性能对比示例：使用
input()和print()使用
sys.stdin.readline()和sys.stdout.write()import time import sys start_time = time.time() for _ in range(1000000): line = sys.stdin.readline().strip() sys.stdout.write(line + '\n') end_time = time.time() print("Time taken:", end_time - start_time)
代码
代码1
n, m, k = map(int, input().split())
a = []
for i in range(n):
a.append(list(map(int, input().split())))
b = []
for i in range(k):
b.append(list(map(int, input().split())))
c = [[0] * (m + 1) for i in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
c[i][j] = c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1] + a[i - 1][j - 1]
for i in range(k):
x1, y1, x2, y2 = b[i][0], b[i][1], b[i][2], b[i][3]
print(c[x2][y2] - c[x1 - 1][y2] - c[x2][y1 - 1] + c[x1 - 1][y1 - 1])代码2
import sys
# 使用 sys.stdin.readline() 读取输入
n, m, k = map(int, sys.stdin.readline().split())
a = []
for i in range(n):
a.append(list(map(int, sys.stdin.readline().split())))
b = []
for i in range(k):
b.append(list(map(int, sys.stdin.readline().split())))
# 构建前缀和数组
c = [[0] * (m + 1) for i in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
c[i][j] = c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1] + a[i - 1][j - 1]
# 使用 sys.stdout.write() 输出结果
for i in range(k):
x1, y1, x2, y2 = b[i][0], b[i][1], b[i][2], b[i][3]
sys.stdout.write(str(c[x2][y2] - c[x1 - 1][y2] - c[x2][y1 - 1] + c[x1 - 1][y1 - 1]) + '\n')