详解前缀和与差分问题

文章目录

• 详解前缀和与差分问题
• • 概念
  • • 一维前缀和
    • • 经典题目
    • 一维差分
    • • 经典题目
    • 二维前缀和
    • • 经典题目
    • 二维差分数组
  • 应用场景（适用条件）
  • 解题步骤
  • 例题
  • • Leetcode-497-random point
    • Leetcode-327-Count of Range Sum 🌟🌟🌟🌟🌟

知乎-前缀和

前缀和与差分（超详细！！！）

概念

一维前缀和

一维前缀和 S(i) 即前 i 或 i+1 个元素的和，视情况而定是否需要让 S(0) = 0

Eg: [1,2,3,4,5]

如果有 m 次，求 [l,r] 这个区间元素的和：如果每次都遍历则时间复杂度为 O(mn)

若只一次计算出前缀和 [0,1,3,6,10,15]，之后求 [2,3] 区间元素的和即：S(r+1)-S(l)，求其他区间同理，此时时间复杂度为 O(m+n)

经典题目

读入 n 个整数的数列 a1，a2，…，an 和正整数 k（1<=k<=n），请输出连续排列的 k 个整数的和的最大值

class Solution:def maxSum0(self, nums: List[int], k: int) -> int:"""已知 kadane 算法适用于 k 任意的场景，求和最大的子序列，时间复杂度为 O(N)arr = [nums[0]] * lengthfor i in range(1,length):arr[i] = max(arr[i]+nums[i], nums[i])return max(arr)我们还是先用暴力法来看下这个问题：此时时间复杂度为 O(N^2)，空间复杂度为 O(1):param nums::param k::return:"""length = len(nums)if k == length:return sum(nums)res = float('-inf')for i in range(length - k + 1):tmp = nums[i]for j in range(i + 1, i + k):tmp += nums[j]res = max(res, tmp)return resdef maxSum(self, nums: List[int], k: int) -> int:"""我们发现在计算的过程中其实重复了很多次求和操作，因此我们可以尝试使用前缀和来解决这个问题时间复杂度为: O(N)空间复杂度为: O(N):param nums::param k::return:"""summary = [0]length = len(nums)for i in range(length):summary.append(summary[-1] + nums[i])# print(summary)res = float('-inf')for i in range(k, length+1):res = max(res, summary[i] - summary[i - k])return res

一维差分

一维差分 D(i) 即 i 和 i-1 元素的差值

Eg: [1,2,3,4,5]，其差分数组即为 [1,1,1,1,1] 对 [2,3] 区间的元素增加一个值 3，原数组变成了

[1,2,6,7,5] 差分数组变成了 [1,1,4,3,-2] 即只有 l 和 r+1 发生了变化，如果 r+1 大于等于 length 则它不改动，即：

D[l] = D[l]+3

D[r+1] = D[r+1]-3

因此如果原数组均为 0，对原数组修改了 m 次，修改内容是对 [l,r] 区间的元素加某个值或减某个值，有 q 次，求任意个元素的值是多少

暴力解法是对原数组修改 m 次，每次修改 [l,r] 的内容，时间复杂度为 O(mn)

如果利用差分数组，m 次只改动 D[l] D[r+1] 然后拼出原数组即可，时间复杂度为 O(m+n)

for i in range(m):D[l] += add_valD[r+1] -= add_val
arr = [0] * n
arr[0] = D[0]
for i in range(1,n):arr[i] = arr[i-1]+D[i]

经典题目

海底高铁

铁路经过 N 个城市，每个城市都有一个站。不过，由于各个城市之间不能协调好，于是乘车每经过两个相邻的城市之间（方向不限），必须单独购买这一小段的车票。第 i 段铁路连接了城市 i 和城市i+1(1<=i 如果搭乘的比较远，需要购买多张车票。第i段铁路购买纸质单程票需要 Ai 博艾元。
虽然一些事情没有协调好，各段铁路公司也为了方便乘客，推出了 IC 卡。对于第i段铁路，需要花 Ci 博艾元的工本费购买一张 IC 卡，然后乘坐这段铁路一次就只要扣 Bi(Bi Uim 现在需要出差，要去 M 个城市，从城市 P1 出发分别按照 P1,P2,P3…PM 的顺序访问各个城市，可能会多次访问一个城市，
且相邻访问的城市位置不一定相邻，而且不会是同一个城市。
现在他希望知道，出差结束后，至少会花掉多少的钱，包括购买纸质车票、买卡和充值的总费用。

class Solution:def undersea(self, A: List[int], B: List[int], C: List[int], N: int, M: int, P: List[int]) -> int:""":param M: 标识要去的城市个数:param P: 标识依次要去的城市标记           [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]:param N: 标识城市的总个数 9:param A: 标识第 i 段铁路单程票价          [200, 300, 500, 345, 100, 600, 450, 2]:param B: 标识使用 IC 卡后第 i 段铁路的票价 [100, 299, 200, 234, 50, 100, 400, 1]:param C: 标识购买第 i 段铁路 IC 卡的工本费 [50, 100, 500, 123, 100, 1, 80, 10]求最少要花多少钱题目主体思路：计算每段路程要路过的次数，比较每段路程用 IC 卡便宜还是直接买票便宜时间复杂度：O(N)空间复杂度：O(N):return:"""num = [0] * (N + 1)# 3 2 1# 1 2 3 4# 4 3 2 1# 1 2 3 4 5# 5 6 7 8 9# 9 8 7 6 5 4 3 2# 2 3 4 5 6# 6 5# 5 4 3# 我们需要耗费 O(M*N) 的时间复杂度来获取到每段路程经过的次数，但我们在这个循环中可以发现我们其实一直在给 [start,end-1] 区间加一个值# 已知差分数组的特点是，仅 l 改变+add_val 和 r+1 改变-add_val 所以我们可以使用差分数组# for i in range(M - 1):#     start = min(P[i], P[i + 1])#     end = max(P[i], P[i + 1])#     for j in range(start, end):#         num[j] += 1for i in range(M - 1):start = min(P[i], P[i + 1])end = max(P[i], P[i + 1])num[start] += 1num[end] -= 1print("====>D", num)# 差分数组的前缀和即为每段路走过的次数for i in range(1, N):num[i] = num[i] + num[i - 1]res = 0# # [0, 4, 6, 6, 4, 4, 2, 2, 2, -2]print("====>S", num)for i in range(1, N):# 买票的钱：A[i-1]*num[i]# 用 IC 卡 的钱： B[i-1]*num[i]+C[i-1]res += min(A[i - 1] * num[i], B[i - 1] * num[i] + C[i - 1])return res

二维前缀和

主要应用于求二维矩阵和，给定矩阵 arr[i][j] , S 为矩阵和， S[i][j]标识从 arr[0][0] 到arr[i][j] 组成的矩阵的和，其中 S[0][0]=0

S[i][j]=S[i−1][j]+S[i][j−1]−S[i−1][j−1]+arr[i][j]S[i][j] = S[i-1][j]+S[i][j-1]-S[i-1][j-1]+arr[i][j]S[i][j]=S[i−1][j]+S[i][j−1]−S[i−1][j−1]+arr[i][j]

if i == 0:for j in range(1, width):S[0][j] = S[0][j-1] + arr[0][j]
if j == 0:for i in range(1, height):S[i][0] = S[i-1][0] + arr[i][0]

Eg: 给定一个 n*m 大小的矩阵 a，有 q 次询问，每次询问给定 x1,y1,x2,y2 四个数，求以 (x1,y1) 为左上角坐标和 (x2,y2) 为右下角坐标的子矩阵的所有元素和。注意仍然包含左上角和右下角的元素。

暴力解法：每次都遍历则时间复杂度为 O(mnq)

若只一次计算出二维前缀和，之后求以 (x1,y1) 为左上角坐标和 (x2,y2) 为右下角区间元素的和即：

S=S[x2][y2]−S[x2][y1−1]−S[x1−1][y2]+S[x1−1][y1−1]S = S[x2][y2]-S[x2][y1-1]-S[x1-1][y2]+S[x1-1][y1-1]S=S[x2][y2]−S[x2][y1−1]−S[x1−1][y2]+S[x1−1][y1−1]

S(r+1)-S(l)，求其他区间同理，此时时间复杂度为 O(mn+q)

    # 已知二维数组#   0 1 2 3# 0 7 4 6 5# 1 1 3 7 4# 2 6 5 1 3
class Solution:def summary(self, nums: List[List[int]], start: List[int], end: List[int]):height = len(nums)width = len(nums[0])S = [[0] * (width + 1) for _ in range(height + 1)]for i in range(height):for j in range(width):S[i+1][j+1] = S[i+1][j] + S[i][j+1] - S[i][j] + nums[i][j]print('====>', S)res = S[end[0]+1][end[1]+1] - S[end[0]+1][start[1]] - S[start[0]][end[1]+1] + S[start[0]][start[1]]return res

经典题目

leetcode-最大子矩阵

二维差分数组

二维差分数组的前缀和数组就是原数组本身，求二维差分数组需要注意，如果是第一行或者第一列则和一维差分一样，如果是其他列则可以使用 nums[i][j]+nums[i-1][j-1]-nums[i-1][j]-nums[i][j-1]

class Solution:def difference(self, nums: List[List[int]]) -> List[List[int]]:"""求二维差分数组，如果是第一行或者第一列则和一维差分一样，如果是其他列则可以使用nums[i][j]+nums[i-1][j-1]-nums[i-1][j]-nums[i][j-1]:param nums::return:"""height = len(nums)width = len(nums[0])D = [[0] * width for _ in range(height)]D[0][0] = nums[0][0]for i in range(height):for j in range(width):if i == 0 and j == 0:continueif i == 0:D[0][j] = nums[0][j] - nums[0][j-1]elif j == 0:D[i][0] = nums[i][0] - nums[i-1][0]else:D[i][j] = -nums[i][j - 1] - nums[i - 1][j] + nums[i][j] + nums[i - 1][j - 1]return D

当给二维数组的某一区域都添加一个值后，二维差分数组是怎么变化的呢：

假如修改的是 [x1,y1] [x2,y2] 为左上角和右下角的数据，都加了 target，那么此时：

D[x1][y1] += target D[x1][y2+1] -=target

D[x2+1][y1] -= target D[x2+1][y2+1] += target

如果 x2+1 或 y2+1 超过边界那就不需要更改

class Solution:def difference_plus(self, nums: List[List[int]], start: List[int], end: List[int], target: int) -> List[List[int]]:height = len(nums)width = len(nums[0])D = [[0] * width for _ in range(height)]D[0][0] = nums[0][0]for i in range(height):for j in range(width):if i == 0 and j == 0:continueif i == 0:D[0][j] = nums[0][j] - nums[0][j - 1]elif j == 0:D[i][0] = nums[i][0] - nums[i - 1][0]else:D[i][j] = -nums[i][j - 1] - nums[i - 1][j] + nums[i][j] + nums[i - 1][j - 1]x1 = start[0]y1 = start[1]x2 = end[0]x3 = x2 + 1y2 = end[1]y3 = y2 + 1D[x1][y1] += targetif y3 < width:D[x1][y3] -= targetif x3 < height:D[x3][y1] -= targetif y3 < width and x3 < height:D[x3][y3] += targetreturn D

应用场景（适用条件）

前缀和通常被用于一些复杂问题的中间步骤，比如

• 子序列和问题（注意是连续的子序列），对于指定长度的子序列和优先考虑前缀和，对于任意长度的最大子序列和可以使用 kadane 算法
• 二维数组区间和问题
• 指定区间增加固定值问题，此时适合用差分数组来解决

解题步骤

首先审查题目是否符合上述条件，此时列出前缀和或差分数组然后进行运算。

时间和空间复杂度视具体题目确定。

例题

Leetcode-497-random point

这道题既考察对题目的理解也考察了对前缀和以及二分查找的应用，来实际操作一下吧~

github repo

Leetcode-327-Count of Range Sum 🌟🌟🌟🌟🌟

这道题的考察范围很广，既包括分治，又包括前缀和还有双指针的应用

解题过程：已知题目和数组中连续元素的和有关，所以首先求前缀和，但不完全满足需求，因为要求前缀和的不同差值。

如果使用嵌套循环，时间复杂度较高，为了降低时间复杂度我们可以考虑两个有序数组求差值，参考：详解双指针法

此时剩下的问题是如何让数组有序，则使用归并排序即可。

github repo