差分详细讲解笔记

 

那么我们先来细细地讲一下差分到底是个什么东西吧

首先,差分其实和我们所熟悉的前缀和大有相似之处

前缀与差分其实是一对 互逆序列

只是换成了B[i]=a[i]-a[i-1]。

那么我们先来举一个例子看看

假如a数组wei

7  5 2 9 11 19 14

那么差分数列B就为

7 -2 -3 7 2 7 -5

差分数列的前缀和就是原数列

==》同样前缀和数列的差分也是原数列

那么我们再来讲一下差分数列的几个神奇的性质

还是刚才的那个差分数列B

7 -2 -3 7 2 7 -5

如果我们想要在原数组a的[l,r]的区间内把所有的值都加上(减去也行)d

那么差分数列会怎么变化呢

假如从下标从1到7

我们把a [2,5]都加3

那么a数组就变成了

7  8 5 12 14 19 14

那么差分数列会怎么变化呢

首先B[2]肯定是要加上d的,因为原来a[2]比a[1]大的值,a[2]又加了d,那它们的差也会加d

a[3]a[4]a[5]都和它们的前一个数一样,同时加了d,根据等式的基本性质,差还都是不变的,B[3-5]都没有发生改变

而B[6],因为a[6]前一个数a[5]加了d,那a[6]-a[5]也就少了

总结一下:

那么区间的操作就不再复杂,只需要把B[ l ]和B[r+1]的值进行更改就行啦!

加油!它也不难偶~

原文地址:https://www.cnblogs.com/Tidoblogs/p/11108060.html