前缀和以及差分

前言

在写CCF的202109-2题目时,我们宿舍的一位大佬教我怎么使用差分算法来解那道题,可是在他教了我两遍之后,我还是不能理解。然后今天去问了老师,老师跟我说他并没有听说过什么差分!呜呜呜,我当场就懵逼了,老师也给我讲解了一下他的看法,但是我还是不能明白。就在刚刚,我又想了一想,好像突然之间开窍了,好像就理解了,所以我把那题目写了之后,我就接着想把我的理解写出来了,我怕以后我又忘了,又不能理解了,废话不多说了,开始吧!

一维前缀和及差分

先讲什么是前缀和

前缀和,就是这个数字及其前面的数的和,也就是 Sm=a[0]+a[1]+a[2]+···+a[i],(a[0]=0,下面b,c同样如此)我们把Sm叫做a[i]的前缀和,然后用一个数组来存储前缀和的话这个数组就叫前缀和数组,例如: b[i]=a[0]+a[1]+a[2]+···+a[i]

再讲差分

差分就是两数之差,a[i]-a[i-1],就叫做a[i]的差分,同样,也会有一个差分数组,c[i]=a[i]-a[i-1]

差分数组的性质

性质一:我们不难发现,差分数组的前缀和就是原数组在当前位置的具体值,你看: c[1]=a[1]-a[0] c[2]=a[2]-a[1] ··· c[i]=a[i]-a[i-1] 所以,sum=c[1]+c[2]+···+c[i]=a[i]-a[0]=a[i] 性质二:(不懂怎么表述)***** 我们先给一个数组吧 a[ ]={0,1,2,3,4,5,6,7,8,9}; 现在我要对[2,7]范围内的元素都进行+5的操作。那我们当然可以一个一个加,但是这样太麻烦了,我们可以用差分数组来进行操作。设b为a的差分数组,则 b[ ]={0,1,1,1,1,1,1,1,1,1}; 我们对下标为[2,7]的元素都加上5,那么对于2到7的元素来说,他们的差分是不会变的,因为大家都加了5,也就是说,+5这个操作影响的是范围内的值与范围外的值的差分,也就是影响的是临界的时候的差分。 所以,只需对差分数组b[2]+5即可,进行前缀和操作时,2以后的数都会+5,但是我们只是想在[2,7]这个范围+5,并不想影响到下标7以后的数,所以,我们执行b[8]-5,这时,求前缀和的时候7以后的数还和原来一样不受影响。 处理后的差分数组: b[ ]={0,1,6,1,1,1,1,1,-4,1}; 求前缀和: a[ ]={0,1,7,8,9,10,11,8,9}; 你看,这不就相当于对下标[2,7]的数都加上了5嘛!

所以,当我们要对一个范围内的数全体加上或减去某个值时,我们可以对它的差分数组进行操作。具体操作就是:

1
2
3
void add(int l, int r,int n) {
    diff[l]+n, diff[r+1]-n;//l为下界,r为上界
}

再来一次,对下标为[1,5]的数全体+1,这时执行

1
add(1,5,1);

这时: b[ ]={0,2,6,1,1,1,0,1,-4,1}; a[ ]={0,2,8,9,10,11,11,8,9}; 同样的,**无论我们执行多少次操作,我们只要对差分数组进行操作即可,最后再对差分数组求前缀和就能得出最后的结果。**这个就是第二个性质。

以CCF-CSP202109-2为例讲解

题目详细见下面的博文 {% post_link CCF-CSP/202109-2非零段划分 %}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
const int N = 1e6;
int dif[N], a[N];
int n;
void add(int l, int r) { dif[l]++, dif[r + 1]--; }
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        if (a[i - 1] < a[i]) {
            add(a[i - 1] + 1, a[i]);
        }
    }
    int maxn = 0, pre = 0;
    for (int p = 1; p < 1e4; p++) {
        pre += dif[p];
        maxn = max(maxn, pre);
    }
    cout << maxn;
    return 0;
}

当a[i]>a[i-1]时,当p取到这两个数之间的值时,这里会出现一个非零段,也就是非零段加1,这是不是我们上面所说的对一个范围+某个值?这时候我们执行add(a[i-1]+1,a[i])的意思就是,当p取a[i-1]+1到a[i]这些值的时候,非零段会+1;然后我遍历数组,对满足条件的数同样进行上面的差分操作,也就是

1
2
3
4
if (a[i - 1] < a[i]) {
            add(a[i - 1] + 1, a[i]);
            }
            

到了最后,我们求dif的前缀和pre=dif[0]+dif[1]+···+dif[p],这样就可以直接求得dif的最终状态,也就是pre就是当取值为p时的非零段个数。 pre += dif[p];

然后题目要求求出最大的非零段,用maxn记录最大值即可。

CCF-CSP例题补充解释

如果a[i-1]<a[i],这意味这什么?

意味着当我的p取到这个范围内的值的时候,非零段会+1

那如果我开一个很大的数组sum,他的下标表示p的取值,它的内容表示当p取得的值是它的下标时我的非零段个数

那是不是说,上述的这个范围里的值都要进行+1的操作,那这是不是对一个范围内的数都进行+1操作,是不是可以运用差分数组来解决了?那么sum的数组是不是就是dif的前缀和,但是题目并没有要求输出每个p时的非零段个数,那么我就没有必要开一个数组了,就用一个pre来表示sum的前缀和。


二维前缀和

假设我们给定义个二维数组a以及一个坐标(x,y),我们把它左上角的所有元素的和叫做a在(x,y)的前缀和,定义出这样子的一个二维数组,那它就是前缀和数组。

前缀和数组求法:

sum[x][y]=sum[x-1][y]+sum[x][y-1]+a[x][y];

可以用面积来理解,(0,0)->(x,y)的面积=红色围住的面积+蓝色围住的面积—重叠部分的面积

https://i.loli.net/2021/11/02/RVHbeuE79ONJDjA.png

求部分矩阵和

假设我给出前缀和数组,给定两个点(x1,y1)和(x2,y2),他们分别表示一个矩形的左上角和右下角(x1,y1)和(x2,y2),求两点之间的矩形所有的数的和。理解的话看下图,这里给出具体公式:

all=sum[x2][y2]-sum[x2][y1-1]-sum[x1-1,][y2]+sum[x-1][y-1];

https://i.loli.net/2021/11/02/xHSc64uYGJUMhOr.png

二维差分

具体差分数组是怎样定义的好像我也不懂,但这并不影响。 同样的,二位差分数数组适用的条件也是有范围的,我们在一维差分里,我们应用差分数组的条件是在一个连续段上加上或减去某一个数。 在二维中,我们的条件是对一个矩形内的内容进行操作。

下图以及相应引用来自SolitudeAlma

二维差分

从图中我们可以很清楚的看到,如果在x1,y1上加一个数c那么它右下角的数都会加上c,那么该怎么办呢,其实这也是容斥定理。我们只需要减去右边多加的部分和下边多加的部分最后再加上重复减去的部分即可

所以,我们对二位差分数组进行的操作如下:

1
2
3
4
add(int x1,int y1,int x2,int y2,int c){
	dif[x1][y1]+=c,dif[x2+1][y2+1]+=c;
	dif[x2+1][y1]-=c,dif[x1][y1+1]-=c;
}

https://i.loli.net/2021/11/02/fjROeWwkcK6Bao1.png

我只要在图中带框的位置进行加减操作就不会影响到矩形外的元素了

参考资料

https://www.acwing.com/blog/content/5890/ https://chen-ac.blog.csdn.net/article/details/115844025

0%