前缀和与差分讲解

前缀和与差分讲解

前缀和与差分讲解

文章目录

• 前缀和与差分讲解
• • 前缀和
  • • 例题
    • 小结
  • 差分
  • • 例题
    • 小结
  • 遇到的问题及解决

前缀和

数值数组A，前缀和数组S，满足如下定义

S[i] = A[0] + A[1] +…+A[i]

应用：求一段数的和

A[i ~ j] = S[j] - S[i - 1]
使得原本O(n)的操作，只需要O(1)

例题

输入一个长度为 n 的整数序列。

接下来再输入 m 个询问，每个询问输入一对 l,r。

对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。

输入格式
第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示整数数列。

接下来 m 行，每行包含两个整数 l 和 r，表示一个询问的区间范围。

输出格式
共 m 行，每行输出一个询问的结果。

数据范围
1≤l≤r≤n,
1≤n,m≤100000,
−1000≤数列中元素的值≤1000
输入样例：
5 3
2 1 3 6 4
1 2
1 3
2 4
输出样例：
3
6
10

n, m= map(int, input().split())nums = list(map(int, input().split()))s = [0] * (len(nums) + 1)for i in range(1, len(nums) + 1) :s[i] = s[i - 1] + nums[i - 1]for i in range(m) :l, r = map(int, input().split())print(s[r] - s[l - 1])

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

对于每个询问输出子矩阵中所有数的和。

输入格式
第一行包含三个整数 n，m，q。

接下来 n 行，每行包含 m 个整数，表示整数矩阵。

接下来 q 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。

输出格式
共 q 行，每行输出一个询问的结果。

数据范围
1≤n,m≤1000,
1≤q≤200000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000
输入样例：
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

n, m, q = map(int, input().split())arr = []for i in range(n) :arr.append(list(map(int, input().split())))s=[[0]*(m + 1) for _ in range(n + 1)]for i in range(1, n + 1) :for j in range(1, m + 1) :if i == 1 and j == 1:s[i][j] = arr[0][0]elif i ==1 : s[i][j] = s[i][j - 1] + arr[i - 1][j - 1]elif j == 1 :s[i][j] = s[i - 1][j] + arr[i - 1][j - 1]else :s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + arr[i - 1][j - 1]#     print(s[i][j], end=" ")# print()
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])

小结

一些小细节，在于处理边界问题时，可以将前缀数组最外层设为0，方便于统一操作和递推

差分

例题

差分是前缀和的逆过程，假设数组A和数组B，
数组B的前i个元素和恰好等于A数组的第i个元素。我们称B数组为A数组的差分数组

应用：可以对一段连续的数进行统一操作

输入一个长度为 n 的整数序列。

接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r] 之间的每个数加上 c。

请你输出进行完所有操作后的序列。

输入格式
第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示整数序列。

接下来 m 行，每行包含三个整数 l，r，c，表示一个操作。

输出格式
共一行，包含 n 个整数，表示最终序列。

数据范围
1≤n,m≤100000,
1≤l≤r≤n,
−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000
输入样例：
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
输出样例：
3 4 5 3 4 2

n, m = map(int, input().split())a = list(map(int, input().split()))b = [0] * (n + 2)def insert(l, r, c) :global bb[l] += cb[r + 1] -=cfor i in range(1, n + 1) :insert(i, i, a[i - 1])for i in range(m) :l, r, c = map(int, input().split())insert(l, r, c)for i in range(1, n + 1) :b[i] += b[i - 1]for i in range(1, n + 1) :print(b[i], end= ' ')

输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 c。

请你将进行完所有操作后的矩阵输出。

输入格式
第一行包含整数 n,m,q。

接下来 n 行，每行包含 m 个整数，表示整数矩阵。

接下来 q 行，每行包含 5 个整数 x1,y1,x2,y2,c，表示一个操作。

输出格式
共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。

数据范围
1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤c≤1000,
−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1
输出样例：
2 3 4 1
4 3 4 1
2 2 2 2

import copy
n, m, q = map(int, input().split())a = []for i in range(n) :a.append(list(map(int, input().split())))b = [[0] * (m + 2) for _ in range(n + 2)]
def insert(x1, y1 , x2, y2, c) : #要引用全局变量一定要声明global bb[x1][y1] += cb[x2 + 1][y1] -= cb[x1][y2 + 1] -= cb[x2 + 1][y2 + 1] += cfor i in range(1, n + 1) :for j in range(1, m + 1) :insert(i, j, i, j, a[i - 1][j - 1])
for i in range(q) :x1, y1, x2, y2, c = map(int, input().split())insert(x1, y1, x2, y2, c)
# c = copy.deepcopy(b)
c = b[:]
for i in range(1, n + 1) :for j in range(1, m + 1) :b[i][j] = b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1] + c[i][j]print(b[i][j], end=" ")print()

小结

细节方面：由于对于差分数组的初始化需要对左边界进行加操作，对右边界之后进行减操作，所以在初始化差分数组时要将其额外分配空间，此外在回推操作后的数组（即差分数组的前缀和数组）时，将第一位当成边界初始化为0更易操作。

遇到的问题及解决

数组越界问题按下不表：无非是对于索引的不统一。
对于二维数组的初始化收获有点;

一维数组初始化a = [0]*n，复制并拼接了n个0元素，对于每个索引都是特殊的，没毛病
二维数组初始化：

刚开始我是这样初始化的a = [[0] * n] * m,结果当a[0][0] = 1时，所有行的第一位都发生改变：原因是对于a的每一行的复制了同一个[0] * n引用，这属于浅拷贝
正确的打开方式：a = [[] * n for _ in range(m)] //列表解析
函数引用全局变量，一定要声明global