差分

什么是差分：

差分一一种处理数据的巧妙而简单的方法，它应用于区间的修改和询问问题。把给定的数据集A分成多个区间，对这些区间做多次操作，每次操作是对某个区间内的所有元素做相同的加减操作，若一个个地修改区间内的元素，非常耗时。引入差分数组D，当修改某个区间时，只需要修改这个区间的断点，就能记录整个区间的修改，而对端点的修改非常容易，复杂度为O(1)。当所有修改操作结束后，再利用差分数组计算出新的A。

数据A可以是一维线性数组a[]、二维矩阵a[][]、三维立体a[][][]。相应地，定义一维差分数组D[]、二维差分数组D[][]、三维差分数组D[][][]。一维差分容易理解，二维和三维差分需要一点空间想象力。

类似于数学中的求导和积分，差分可以看成前缀和的逆运算。前缀和就是积分、差分就是微分。

差分在写题时候作用：

一般的，差分主要用于让一个序列某一特定范围内的所有值都加上或减去一个常数。

所以差分往往应用于线性的场合，即一维数组的环境，但是除此之外，差分还可以用于二维数组，甚至三维！！！

但是相比一维数组，应用的少。

差分可以简单的看成序列中每个元素与其前一个元素的差。

一维差分

Java模板

1

C++模板

1

二维差分

前缀和

在一维差分中，原数组a[]是从第1个D[1]开始的差分数组D[]的前缀和，a[k]=D[1]+D[2]+…+D[k]。

在二维差分中，a[][]是差分数组D[][]的前缀和，即由原点坐标(1,1)和坐标(i,j)围成的矩阵中，所有D[][]。

推荐例题：

P3397 地毯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)