差分数组知识笔记

使用场景

频繁对某个区间所有元素进行加减相同值，推荐使用差分数组，可以避免每一次计算都把整个区间的元素遍历一遍。

生成差分数组

设差分数组为diff_arr，原数组为source_arr，数组长度为n，其中：
diff_arr[0] = source_arr[0]
diff_arr[i] = source_arr[i] - source_arr[i - 1]，其中1 <= i < n
接下来对diff_arr的区间[1,3]进行加3，我们只要对diff_arr[1]进行+3操作，对diff_arr[4]进行减3操作，总结为：
对区间[i, j]进行加x操作，只需要对diff_arr[i] + x和diff_arr[j + 1] - x

对图中红字做出解释： 这里之所以对diff_arr[4]进行减3，是因为在还原数组的时候，后一项需要加上前一项的值，而我们只对[1, 3]范围内做加3的操作，4并不在操作范围内，所以需要提前减掉3。

复原差分数组

设复原数组为restore_arr，restore_arr第一项与diff_arr第一项相等，即：
restore_arr[0] = diff_arr[0]
restore_arr从第二项开始，restore_arr每一项等于diff_arr的当前项加上复原好的前一项，即：
restore_arr[i] = diff_arr[i] + restore_arr[i - 1]，其中1 <= i < n

Python代码

class DiffArray:# 差分数组def initial(self, nums):# 初始化差分数组n = len(nums)diff = [0] * ndiff[0] = nums[0]for i in range(1, n):diff[i] = nums[i] - nums[i - 1]return diffdef increment(self, diff, i, j, val):# 加减操作diff[i] += valif j < len(diff) - 1:diff[j + 1] -= valdef restore(self, diff):# 恢复数组for i in range(1, len(diff)):diff[i] = diff[i] + diff[i - 1]if __name__ == '__main__':source_arr = [4, 3, 5, 6, 1]obj = DiffArray()diff_arr = obj.initial(source_arr)  #初始化差分数组obj.increment(diff_arr, 1, 3, 3)  # 区间[1, 3]做+3操作obj.restore(diff_arr)print(diff_arr)