前缀和与差分

2024-03-11 11:10:49

前缀和与差分的定义

前缀和的定义比较简单，对于一个序列 a i , b i a_i,b_i ai,bi有下列的定义， b i = a 1 + a 2 + a 3 + ⋅ ⋅ ⋅ + a i ， a i = b i − b i − 1 b_i=a_1+a_2+a_3+···+a_i，a_i=b_i-b_{i-1} bi=a1+a2+a3+⋅⋅⋅+ai，ai=bi−bi−1，则称 b b b为 a a a的前缀和， a a a为 b b b的差分。显然这两种是互逆操作。

前缀和的应用

前缀和基本上只有一个作用，就是求快速求某个区间的和

一维前缀和

b l = a 1 + a 2 + a 3 + ⋅ ⋅ ⋅ + a l b_l=a_1+a_2+a_3+···+a_l bl=a1+a2+a3+⋅⋅⋅+al
b r = a 1 + a 2 + a 3 + ⋅ ⋅ ⋅ + a r b_r=a_1+a_2+a_3+···+a_r br=a1+a2+a3+⋅⋅⋅+ar
b r + 1 = a 1 + a 2 + a 3 + ⋅ ⋅ ⋅ + a r + 1 b_{r+1}=a_1+a_2+a_3+···+a_{r+1} br+1=a1+a2+a3+⋅⋅⋅+ar+1
我们想求 [ l , r ] [l,r] [l,r]的区间之和，即 a l + a l + 1 + ⋅ ⋅ ⋅ + a r a_l+a_{l+1}+···+a_r al+al+1+⋅⋅⋅+ar，我们可以用 b r + 1 − b l b_{r+1}-b_l br+1−bl来求（直接相减就可以得出）。
具体代码如下：

二维前缀和

b x 2 y 2 = ∑ i = 1 x 2 ∑ j = 1 y 2 a i j b_{{x_2}{y_2}}=\sum\limits_{i=1}^{x_2}\sum\limits_{j=1}^{y_2}{{a_{ij}}} bx2y2=i=1∑x2j=1∑y2aij

b x 1 x 2 = ∑ i = 1 x 1 ∑ j = 1 y 1 a i j b_{{x_1}{x_2}}=\sum\limits_{i=1}^{x_1}\sum\limits_{j=1}^{y_1}{{a_{ij}}} bx1x2=i=1∑x1j=1∑y1aij
b x 2 y 1 − 1 = ∑ i = 1 x 2 ∑ j = 1 y 1 − 1 a i j {b_{{x_2}{{y_1-1{}}}}}=\sum\limits_{i=1}^{x_2}\sum\limits_{j=1}^{y_1-1}{{a_{ij}}} bx2y1−1=i=1∑x2j=1∑y1−1aij
b x 1 − 1 y 2 = ∑ i = 1 x 1 − 1 ∑ j = 1 y 2 a i j b_{{{x_1}-1}{y_2}}=\sum\limits_{i=1}^{x_1-1}\sum\limits_{j=1}^{y_2}{{a_{ij}}} bx1−1y2=i=1∑x1−1j=1∑y2aij
若想求 ( x 1 , y 1 ) (x_1,y_1) (x1,y1)到 ( x 2 , y 2 ) (x_2,y_2) (x2,y2)中区域的和，可用 b x 2 y 2 − b x 1 − 1 y 2 − b x 2 y 1 − 1 + b x 1 y 1 b_{{x_2}{y_2}}-b_{{{x_1-1}}{y_2}}-b_{{x_2}{y_1-1}}+b_{{x_1}{y_1}} bx2y2−bx1−1y2−bx2y1−1+bx1y1来求。

具体代码如下：

求前缀和的代码

for(int i=1;i<=n;i++){ //
    for(int j=1;j<=m;j++){
        b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
    }
}

求区间面积的代码

res=b[x2][y2]-b[x2][y1-1]-b[x1-1][y2]+b[x1-1][y1-1];

差分的应用

差分主要用于对某一区间同时进行加法的操作。

一维差分

有公式 a l = b l − b l − 1 a_l=b_l-b_{l-1} al=bl−bl−1，对 b l b_l bl加 c c c，则有 a l + c , a l + 1 + c , a l + 2 + c , ⋅ ⋅ ⋅ a_l+c,a_{l+1}+c,a_{l+2}+c,··· al+c,al+1+c,al+2+c,⋅⋅⋅
若想要对 [ L , R ] [L,R] [L,R]中的元素加c，只需要对 b l + c b_l+c bl+c，然后 b r + 1 − c b_{r+1}-c br+1−c，然后对 b b b数组求前缀和就可以的出加 c c c操作后的 a a a数组

代码如下：

对差分数组进行插入操作

void insert(int l,int r,int c){
    b[l]+=c;
    b[r+1]-=c;
}

二维差分

二维差分的推理比较难写，大体就是先差分后求前缀和，这里直接给出代码：

在差分数组中进行插入操作

void insert(int x1,int y1,int x2,int y2,int c){
    b[x1][y1]+=c;
    b[x1][y2+1]-=c;
    b[x2+1][y1]-=c;
    b[x2+1][y2+1]+=c;
}

求前缀和

for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
        }
    }

小结

这里有一个重点：我们对差分数组进行初始化的时候可以用插入操作直接完成
一维的有insert(l,l,c)
二维的有insert(x,y,x,y,c)

码农公寓