因为真的菜的要命,连基本的差分操作都搞不明白
很久以来一直没有搞懂差分数组的具体的操作情况,现在通过一定的整理得到详细的解释如下:
假设当前有一数组arr
差分数组则为
arr[1]-arr[0]
arr[2]-arr[1]
arr[3]-arr[2]
arr[4]-arr[3]
所谓差分数组的作用,其实就是对整个数组进行操作时,实现进一步的优化
第一个操作
假设区间1-4内每个数+1
普通方法:枚举全部区间,并对区间内的每个数依次操作
也就是说
如果用差分操作
故只需要修改arr[1]和arr[5]的差分,操作为
arr[1]++;
arr[5]--;
具体为何这样操作,解释如下:
对于差分,我们还是回归到他本质的定义上来
显然我们会发现,只有区间头或区间尾才发生了改变,也就有了上述的操作
用差分数组来推断某一位置的值
这就需要我们从前往后遍历递推
如第一张图的样子所示
arr[3]=-1+arr[2]=差分3+arr[2]
arr[2]=3+arr[i]=差分2+arr[1]
由此我们能够推导出公式,假设差分数组为b[i]
arr[i]=b[i]+arr[i-1]
对应的推导关系如下:
对应的几个例题:
Acwing 797差分
https://www.acwing.com/problem/content/799/
Acwing 2041干草堆
https://www.acwing.com/problem/content/2043/