算法之差分

发表于 | 更新于: | 分类于 ， | | 阅读数
字数统计: 295 | 阅读时长 ≈ 1

前文讲到前缀和适用于原始数组不变，频繁查询某个区间的累加和

而今天要讲的差分，则适用于频繁对原始数组的某个区间的元素进行增减

同样都是维护一个区间，差分和线段树有什么区别呢?

  • 差分适用于范围更新，单独查询

  • 线段树适用于单点跟新，范围查询

构造差分数组

1
2
3
4
5
6
nums=[1,3,5,7,9]
n=len(nums)

diff=[nums[0]]
for i in range(1,n):
    diff.append(nums[i]-nums[i-1])

反推原始数组

通过差分数组反推出原始数组

1
2
3
ori=[diff[0]]
for i in range(1,n):
    ori.append(ori[-1]+diff[i])

熟悉吗?

没错，差分数组的前缀和，就是原始数组

同理，前缀和的差分数组，也是原始数组

区间增减

如果想对区间 nums[i..j] 的元素全部加 a：

1
2
3
diff[i] += a	

diff[j+1] -= a

  • diff[i] += a，相当于nums[i:]的元素全部增加了a

  • diff[j+1] -= a，相当于nums[j+1:]的元素全部减少了a

两式叠加，即相当于nums[i..j] 的元素全部加 a

不要打赏，只求关注呀QAQ