差分数组的学习
文章目录
- 1.差分数组的应用场景
- 2.如何构造一个差分数组
- 2.1 原数组转换为差分数组
- 2.2 差分数组还原为原数组
- 3.差分数组的特性
1.差分数组的应用场景
需要频繁对某个区间的数组进行增减操作
2.如何构造一个差分数组
2.1 原数组转换为差分数组
# 存在一个数组Nums,求出他的差分数组
diff = [0] * len(nums)
diff[0] = nums[0]
for i in range(1, len(nums)):
diff[i] = nums[i] - nums[i-1]
2.2 差分数组还原为原数组
res = [0] * len(diff)
res[0] = nums[0]
for i in range(1, len(diff)):
res[i] = res[i-1] + diff[i]
3.差分数组的特性
如果想对nums[i, j] 范围的数组加3
只需要对差分数组的diff[i] + 3, diff[j+1]-3即可
还原后的nums就是[i,j]范围内加3的结果