差分思想详解

举个例子，有一个数组 a[]={ 1,5,3,7,2,8 } ，他的差分数组就是 b[]={ 1,4,-2,4,-5,6 }

想必你也很快发现了他们之间的联系，b_i=a_i-a_{ i-1 } ，因此可以推出 a_i=b_1+b_2+b_3+...+b_i 。

当我们把 a_{2} 到 a_5 都加上 2 后，数组 a 就变成了 a[]={ 1,7,5,9,4,8 }

然后我们在重新计算一下 b 数组，计算结果是这样的： b[]={ 1,6,-2,4,-5,4 }

有发现什么规律吗？

是的，当 a 数组的 a_{2} 到 a_5 改变了数值后，b 数组只有 b_2 和 b_6 发生了变化，并且变化也是有规律的， b_2加了2 ， b_6 减了 2，因此，我们就可以用差分数组来记录原数组的数值变化，那如何记录变化呢？用前缀和

让我们一起来计算一下 b 数组在变化后的前缀和，计算结果是这样的：q[]={ 0,2,2,2,2,0 }

没错！刚好就是 a 数组变化的数值。

现在知道差分思想了吧，就是用差分数组记录原数组的变化，当需要询问a是把原数组和差分数组的前缀和加起来，就可以了，这种思想用法很广，时间复杂度比直接修改要低，值得一学~

有疑问可以在评论区提出，如果对你有帮助就点个赞再走呗~