差分，即前缀和的逆运算，两者之间的关系类似于数学中的求导和积分的关系。

差分（一维差分）

输入一个长度为 n 的整数序列。

(资料图片)

接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r] 之间的每个数加上 c。

输出进行完所有操作后的序列。

输入格式

第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示整数序列。

接下来 m 行，每行包含三个整数 l，r，c，表示一个操作。

输出格式

共一行，包含 n 个整数，表示最终序列。

差分思路

现有前缀和数组：

a[1], a[2], a[3], ... , a[n]

那么构造差分数组：

b[1], b[2], b[3], ... , b[n]

且使得

a[1]= b[1]

a[2]= b[1]+b[2]

a[3]= b[1]+b[2]+b[3]

...

a[i]= b[1]+b[2]+...+b[i]

对一般用来快速操作整个数组，比如把c加到一个数组的[l，r]部分的所有数据上。相较于时间复杂度至少为O(n)的暴力方法，差分算法可以将时间复杂度降低到O(1)。

对于[l, r]+c的情况，先用前缀和的思路去考虑一下。

假如现b[l]加上c变成b[l]+c, 那么

a[l]也会自动加上c(a数组是b数组的前缀和)，且a[l]及之后的数组都会加上c。

[l, n]+c情况基本如下

差分数组：b[1], b[2], b[l]+c, ... , b[n]

前缀和数组：a[1], a[2], a[l]+c, ... , a[n-1]+c, a[n]+c

由于实际的需求是[l,r]

所以需要把r之后的数全部减去c

即在b数组的r+1之后的数全部减c

如此一来

差分数组：b[1], b[2], b[l]+c, ... ,b[r], b[r+1]-c, ..., b[n-1],b[n]

前缀和数组：a[1], a[2], a[l]+c, ... , a[r]+c, a[r+1], ...,a[n-1], a[n]

差分过程

构建差分数组

区间[l, r]范围内加上需要的c

前缀和运算

insert就是在实现差分。

此外，特别强调：

b[i]+=b[i-1]

由于需要“输出最终整数序列”，所以需要进行前缀和操作，使b[i][j]变成新的a[i][j]。

而这条怎么来的呢？

在一维前缀和中，可知

S[i]=S[i-1]+a[i] 

而在这里，S[i][j]就是新的b[i][j]，a[i][j]就是原来的b[i][j]

差分矩阵（二维差分）

输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 c。

将进行完所有操作后的矩阵输出。

输入格式

第一行包含整数 n,m,q。

接下来 n 行，每行包含 m 个整数，表示整数矩阵。

接下来 q 行，每行包含 5 个整数 x1,y1,x2,y2,c，表示一个操作。

输出格式

共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。

差分矩阵的思路

与前缀和矩阵相同，差分矩阵同样用到了“容斥原理”的思想，即先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复。

假设需要给（x1,y1）(x2,y2)的子矩阵中的数全部加上c。, , , 

那么b[x1][y1]+c就会使如下蓝色部分全部加c。（大于等于x1,y1的部分分别加c）

同理，范围过大，还需要删除不必要的部分，即减去c。

在删除多余部分的时候，基于容斥原理，还要重新补充重复删除的部分

差分矩阵过程

构建差分数组

在矩阵（x1,y1)(x2, y2)范围内加上需要的c

前缀和运算

此外，特别强调：

b[i][j]+=b[i-1]b[j]+b[i][j-1]-b[i-1][j-1]

由于需要“将进行完所有操作后的矩阵输出”，所以需要进行前缀和操作，使b[i][j]变成新的a[i][j]。

而这条怎么来的呢？

在二维前缀和中，可知

S[i,j]=S[i,j−1]+S[i−1,j]−S[i−1,j−1]+a[i,j] 

而在这里，S[i][j]就是新的b[i][j]，a[i][j]就是原来的b[i][j]

总结，对于差分，只用考虑如何更新而非考虑如何构造。

关键词： 如此一来