【算法】前缀和与差分

2024-07-19 30

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 算法学习——前缀和与差分（含一维和二维）

1. 一维前缀和

1.1 定义

前缀和是一段序列里面前n项和。

例如，给定一个一维数组a，它的前缀和s[i]表示第1个元素到第i个元素的总和。也就是s[i]=a[1]+a[2]+a[3]+...+a[i-1]+a[i]

1.2 计算方法

s[i]=s[i-1]+a[i]
需要注意的是，数组的下标都是从1开始的！！！

1.3 作用

通过使用前缀和算法，可以在 O(1) 的时间复杂度内计算出任意区间的和，而不需要遍历整个区间。这对于多次查询区间和的场景非常有用，在处理一些数据范围较大的问题时非常高效。

1.4 适用场景

一个长度为n的数组a，m次询问，每次的询问区间是[l,r]，求区间内所有数的和。

在没学过前缀和之前，对于求一段区间的和，我们的想法就是通过遍历这个区间的所有元素，直接暴力求解：

for (int i = l; i <= r; i++) {
   
    s += a[i];
}

这样直接遍历求和的做法时间复杂度是O(N)。如果再有m次询问，就需要两重循环求解，时间复杂度就为O(N*M)，这样的时间复杂度非常高。

这时我们就可以用前缀和算法，通过O(1)的时间复杂度，直接求出某段区间的和。

具体做法：

首先做一个预处理，定义一个数组s，s[i]表示数组第1个元素到第i个元素的和。

求前缀和：

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

查询求区间和：

区间和为s[r]-s[l-1]

例如下图就表示了区间[3,5]的区间和。

即s[5]-s[2]

while (m--) {
   
    int l, r;
    cin >> l >> r;
    cout << s[r] - s[l - 1] << endl;
}

1.5 模板题

AcWing 795. 前缀和

原题链接：https://www.acwing.com/problem/content/797/

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+10;
ll a[N],s[N];

int main(){
   
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;i++){
   
        cin>>a[i];
        s[i]=s[i-1]+a[i];  //求前缀和
    }

    while(m--){
   
        int l,r;
        cin>>l>>r;
        cout<<s[r]-s[l-1]<<'\n';  //求区间和
    }
    return 0;
}

1.6 总结

2. 二维前缀和

2.1 定义

一个二维数组a，它的前缀和二维数组s[i][j]表示以（1,1）为左上角元素，以（i，j）为右下角元素的矩形块中所有元素的总和。

2.2 计算方法

s[i][j]=a[i][j]+s[i][j-1]+s[i-1][j]-s[i-1][j-1]

2.3 模板题

AcWing 796. 子矩阵的和

原题链接：https://www.acwing.com/problem/content/798/

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1010;
ll a[N][N],s[N][N];

int main(){
   
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m,q; cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
   
        for(int j=1;j<=m;j++){
   
            cin>>a[i][j];
            s[i][j]=a[i][j]+s[i][j-1]+s[i-1][j]-s[i-1][j-1]; //求二维前缀和
        }
    }
    while(q--){
   
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]<<'\n';  //求出子矩阵的和
    }
    return 0;
}

2.4 总结

3. 一维差分

3.1 定义

差分：很少的询问，但有很多改变数组的操作，每次让不同区间[l，r]内的每个数都加c或者减c

差分是前缀和的逆运算

3.2 差分数组

如果我们要对一个数组分成很多区间，对这些区间做多次操作，每次操作是对某个区间内的所有元素做相同的加减操作，若一个个地修改区间内的每个元素，非常耗时。

这里我们就引入“差分数组”的概念。

差分数组，顾名思义，就是由原数组的两个元素作差得到。

这里我们令原数组为a，数组长度为n，再引入一个数组d表示差分数组，那么我们就可以通过遍历数组a，从而求得差分数组d。

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

差分数组的前缀和是原数组

3.3 差分标记

假设我们要修改的区间为[l，r] ，差分数组为d，我们要让[l，r]区间的每个数都加c。

我们就打标记：

d[l] += c;
d[r + 1] -= c;
原理：某一位+c，会把这个操作带到后面。

3.4 作用

引入差分数组d，当修改某个区间时，只需要修改这个区间的端点，就能记录整个区间的修改，而对端点的修改非常简单，复杂度为O(1)。

当所有修改操作结束后，再利用差分数组计算出新的原数组。

3.5 适用场景

长度为n的数组a，1次询问，m次操作，每次令区间[l，r]的每个数+c或-c。

3.6 模板题

AcWing 797. 差分

原题链接：https://www.acwing.com/problem/content/799/

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+10;
ll a[N],d[N];

int main(){
   
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;i++) {
   
        cin>>a[i];
        d[i]=a[i]-a[i-1];  //求差分数组
    }

    while(m--){
   
        int l,r,c;
        cin>>l>>r>>c;
        d[l]+=c;  //差分标记
        d[r+1]-=c;
    }

    for(int i=1;i<=n;i++){
   
        d[i]=d[i-1]+d[i];  //差分数组前缀和
        cout<<d[i]<<' ';
    }
    return 0;
}

4. 二维差分

4.1 定义

n行m列的矩阵，左上角数组元素坐标为(x1，y1)，右下角数组元素坐标为(x2，y2)，1次询问，m次操作，每次操作让矩阵的所有元素都加c或者减c。

4.2 差分数组

设原数组为n行m列的二维数组a，差分数组为d。

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

4.3 差分标记

假设我们要修改的矩阵的左上角元素坐标为(x1，y1)，右下角坐标为(x2，y2),差分数组为d，我们要让这个矩阵内的每个数都加c。