差分(仅Z可观看!)

1.前缀和指一个数组的某下标之前的所有数组元素的和（即数列的前n项求和），前缀和是一种重要的 预处理，能够降低算法的时间复杂度，可以快速地求出某一段的和，对于处理区间之间的问题是往往十分 高效。

对一维数组，可以将其前i个元素的和存入sum数组中，这样，每次调用[l,r]区间的和时，只用求 sum[r]-sum[l-1]就可以得到区间和了。

二维前缀和预处理公式 ：

s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j] 2.差分的应用主要是用于处理区间问题。当某一个数组要在很多不确定的区间，加上相同的一个数。 我们如果每个都进行加法操作的话，那么复杂度 O(nm) 是平方阶的，非常消耗时间。

一维差分结论 ：

给a数组中的[ l, r] 区间中的每一个数都加上c,只需对差分数组b做 b[l] + = c, b[r+1] - = c 。时间复杂度 为O(1), 大大提高了效率。

对于一个给定的二维数组 a[ ][ ]，它的二维差分数组 b[i][j] 可以用如下公式计算： ① b[0][0]=a[0][0]

② b[0][j]=a[0][j]-a[0][j-1]

③ b[i][0]=a[i][0]-a[i-1][0]

④ 递推式：b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]

上述公式是通过二维数组 a是二维差分数组的前缀和这个条件推导出来的

b[x1][y1] += c ; 让整个a数组中蓝色矩形面积的元素都加上了c。

b[x1][y2+1] -= c ;

让整个a数组中绿色矩形面积的元素再减去c， 使其内元素不发生改变。

b[x2+1][y1] -= c ; 让整个a数组中紫色矩形面积的元素再减去c， 使其内元素不发生改变。

b[x2+1][y2+1] += c ; 让整个a数组中红色矩形面积的元素再加上c，

红色内的相当于被减了两次，再加上一次c，才能使其恢复。