前缀和:差分数组

理解什么是差分数组

了解什么是差分数组。

为什么要用差分数组

区间[a,b]内覆盖了n个数

放个例题方便理解:2848. 与车相交的点

先来说说为什么要用差分数组。

假设给定存放着n个区间[a,b]的数组,现在要统计这在n个区间一共出现了多少个数。

比如给了一个数组

[1,2],[2,2],[1,3],[6,9]

那么该区间内一共出现了以下这几个数,这里一共是7个数

1,2,3,6,7,8,9

那怎么求呢?如果直接暴力的话思路可以是

  • 新建一个数组result用来维护出现过的值。再遍历每一个区间,每出现过一次就更新一次result,最后再对result数组进行统计。

对于上面例子中的[1,2]和[1,3],如果用暴力方法的话[1,2]区间就会被遍历两次。如果把[1,2]改为[1,999999],那效率将会低的惊人。

所以我们引入了“差分数组”,用于维护0-n区间每个数在对应区间出现的次数。

什么是差分数组

diff[left] – diff[right+1]区间的前缀和

对于上面的例子

[1,2],[2,2],[1,3],[6,9]

我们新建一个数组diff,数组大小为11(0-10),并初始化值为0。

对于[1,2],我们令diff[1]+=1,diff[2+1]-=1。它表示“1”作为左区间值出现了一次,而3没有在区间内出现。那么此时对diff的每一项求和,当diff[x]的和大于0时,表示x存在于区间中。如果某个时刻前缀和等于0或者小于0,则表示此时的x不存在区间中。

对于[2,2],diff[2]+=1,diff[2+1]-=1,此时diff的数据如下

  • diff[0]=0
  • diff[1]=1
  • diff[2]=1
  • diff[3]=-2
  • diff[4]=0

对于[1,3],diff[1]+=1,diff[3+1]-=1,此时diff如下

  • diff[0]=0
  • diff[1]=2
  • diff[2]=1
  • diff[3]=-2
  • diff[4]=-1

此时对diff求前缀和。sum(diff[1])=2>0,所以1出现在区间中;sum(diff[2])=3>0,所以2出现在区间中;sum(diff[3])=1>0,所以3出现在区间中;sum(diff[4])=0,所以4不在区间中。

以此类推,那么最后对diff的每一项求和,就可以得到区间内出现了多少个数。

写者注

这块有点”只可意会不可言传“的意思。我反正看别人的思路是没看懂,最后自己上手写了下例题才搞懂为啥要用差分数组diff。而且感觉这种题可能有很多变形啊,因为最后求前缀和是对整个diff数组求,之后再看看能不能碰到变形题练练手。
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
在此留下你的评论x