了解什么是差分数组。
为什么要用差分数组
区间[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数组求,之后再看看能不能碰到变形题练练手。