1.思路

基本思路是提前构建好一个前缀和的数组
每次求和都遍历原数组，每次时间复杂度为O(n)
建立一次前缀和数组，每次求和从前缀和数组中查询，每次时间复杂度为O(1)

2.前缀和

输入一个长度为 n 的整数序列。
接下来再输入 m 个询问，每个询问输入一对 l,r。
对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。

步骤

（1）构造前缀和数组： Si = a1 + a2 + ... + ai
（2）求前缀和：[ l, r ] = S(r) - S(l - 1)

*建议前缀和数组下标从1开始，S0定义为0，在代码编写中会更方便，子矩阵的和同理

输入样例：

5 3
2 1 3 6 4
1 2
1 3
2 4

输出样例：

3
6
10

Python3：

inp = input().split()

n, m = int(inp[0]), int(inp[1])

a = input().split()

s = [0]

for i in range(n):
    
    s.append(s[i] + int(a[i]))


for i in range(m):
    
    inp = input().split()
    
    l, r = int(inp[0]), int(inp[1])
    
    print(s[r] - s[l - 1])

3.子矩阵的和

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

步骤

（1）构造矩阵：

     S(i, j) 是左上角所有数的和
     S(i, j) = S(i - 1, j) + S(i, j - 1) - S(i - 1, j - 1) + a(i , j)

（2）求子矩阵的和：

     （x1, y1) (x2, y2) = S(x2, y2) - S(x1 - 1, y2) - S(x2, y1 -1) + S(x1 - 1, y1 - 1)

输入样例：

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

输出样例：

17
27
21

Python3：

inp = input().split()
n, m, q = int(inp[0]), int(inp[1]), int(inp[2])

a = [[0 for j in range(m + 1)] for i in range(n + 1)]
s = [[0 for j in range(m + 1)] for i in range(n + 1)]

for i in range(n):
    inp = input().split()
    for j in range(m):
        a[i + 1][j + 1] = int(inp[j])
        s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + a[i + 1][j + 1]
        
for n in range(q):
    inp = input().split()
    x1, y1, x2, y2 = int(inp[0]), int(inp[1]), int(inp[2]), int(inp[3])
    print(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1])