【编程笔记】差分·差分矩阵
差分，即前缀和的逆运算，两者之间的关系类似于数学中的求导和积分的关系。
差分（一维差分）
输入一个长度为 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
前缀和运算
puts()函数的作用与语句printf("%s\n",s)的作用相同
此外，特别强调：
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]
总结，对于差分，只用考虑如何更新而非考虑如何构造。
