二维差分与二维前缀和

推荐模板题:[USACO19FEB]Painting The Barn

差分与前缀和互为逆运算,即差分数组的前缀和数组为原数组,前缀和数组的差分数组为原数组.二者都利用了容斥原理,这一点在二维平面(或者二维数组)中体现的更加明显.

那么我们先来讲二维前缀和

二维前缀和

一维的前缀和数组是求从数组的首项加到当前项的和,即:
$$
sum[i]=\sum_{j=1}^{i}a[j]=(\sum_{j=1}^{i-1}a[j])+a[i]=sum[i-1]+a[i]
$$
这就是一维前缀和的递推方法.
那么二维的前缀和,我们定义为以二维数组的首行首列(即左上角)元素为左上角,当前位置元素为右下角的矩阵的元素和.当我们推到$(i,j)$时,我们考虑该怎么计算$sum[i][j]$.由于左上角已经固定,我们只考虑右下角.当右下角为$(i,j-1)$时,这是一个$(i,j)$左侧的矩阵,当右下角为$(i-1,j)$时,这表示一个$(i,j)$上方的矩阵.那么如果我们要求$(i,j)$左上方所有元素的和,是不是只要将这两个已经计算好的矩阵和加起来,再加上$a[i][j]$就行了呢?

当然不是.

因为左侧的矩阵和上方的矩阵有一个重合部分,即一个以$(i-1,j-1)$为右下角的,完全位于$(i,j)$左上方的矩阵,直接相加时它被计算了两次,因此我们要把它减去.即:
$$
sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j]
$$

么这就是二维前缀和,求某个矩阵的和的时候过程与此类似.

二维差分

一维的差分是指每一项比前一项多多少,即:
$$
cf[i]=a[i]-a[i-1]
$$
通过差分数组和树状数组可以实现快速的区间加减,也就是使$cf[l]+v,cf[r+1]-v$(注意$r$要$+1$).当我们要求回复正常形式的数组的时候,只需要求前缀和就可以了,即:
$$
a[i]=cf_sum[i-1]+cf[i]
$$
那么二维差分呢?它只不过是在一维差分上又加了一维而已.它的递推公式是这样的:
$$
cf[i][j] = a[i][j]-a[i][j-1]-a[i-1][j]+a[i-1][j-1]
$$
即当前元素减去左边元素再减去上边元素再加上左上角元素.

那么由二维差分数组要求出原数,只需要求出二维前缀和即可.通过二维差分可以快速实现矩阵加减.