前缀和以及差分

2021-10-16

前言

在写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,7,1,1,1,1,1,-4,1};
求前缀和:
a[ ]={0,1,8,9,10,11,12,8,9};
你看,这不就相当于对下标[2,7]的数都加上了5嘛!

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

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

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

add(1,5,1);

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

以CCF-CSP202109-2为例讲解

题目详细见下面的博文
https://www.cnblogs.com/yongcheng137blogs/p/15396599.html

#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;然后我遍历数组,对满足条件的数同样进行上面的差分操作,也就是

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还记录最大值即可。