懂视

三、差分与二维差分

2024-11-07 14:57:14

差分是前缀和的逆运算,主要用于多次对某段区间进行+c操作。首先,求出前缀和逆运算的数组b[i]=a[i]-a[i-1]。接着,若要对[l,r]区间内进行+c操作,只需对b数组中b[l]+=c和b[r+1]-=c。最后,对b数组求一遍前缀和,即可得到原数组通过多次加和操作后的数组。二维差分是二维前缀和的逆运算。建立二维差分数组时,利用容斥原理。对二维数组的某一块区域进行+c操作,只需对二维差分数组执行以下操作:b[x2+1][y2+1]+=c,b[x1][y1]+=c,b[x1][y2+1]-=c,b[x2+1][y1]-=c。最后,求出二维差分数组的二维前缀和数组,即得到原数组通过多次加和操作后的样子。代码实现如下。