算法

前缀和与差分

#前缀和 #差分

导航

前缀和和差分其实更像是一种思想

一维前缀和

先来讲前缀和。所谓前缀和，就是前 i 个数的和，用一个数组 s 来记录： s[i] = a[1]+a[2]+...+a[i]（这很像高中数学数列的前n项的和 其实就是）

下面一个前缀和的应用：

输入一个长度为 n 的整数序列
接下来再输入 m 个询问，每个询问输入一对 l,r 区间（l，r>=1）
对于每个询问，输出原序列中从第 l 个数到第 r 个数的和

下面是实现代码（为了方便看懂，我使用了两个数组，实际上这个问题只要一个就好了）

#include<iostream>

using namespace std;

const int N=1000;

int a[N],s[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //输入n个数，查询m次索引区间[l,r]的和(l>=0,r>=0)
    int n, m;
    cin>>n >> m;
    for(int i=1; i<=n; ++i) cin>>a[i];

    //前缀和
    for(int i=1; i<=n; ++i){
        s[i]= s[i-1]+ a[i];
        //也可以直接采用一个数组就实现前缀和 a[i]= a[i-1]+ a[i]; 前提是原数组不再被使用了
    }

    while(m--){
        int l, r; //l，r均为一段1-base区间
        cin>>l >>r;
        cout<< s[r]-s[l-1] << '\n';
    }
}

依旧解释核心部分

核心代码

for(int i=1; i<=n; ++i){//这里就是在实现前缀和
    s[i]= s[i-1]+ a[i];
}

s[i]的含义就是前i个数的和（前缀和）

这里有个建议：下标从 1 开始存储数组（1-base），这样 s[0] 自然就是 0，查询 [1,r] 的时候当 l = 1 的时候不会越界也不用特判边界

cout<< s[r]- s[l-1];

前缀和最经典的应用：O(1) 查询区间和。s[r] 是前 r 个数的和， s[l-1] 是前 l-1 个数的和，两者的差s[r]-s[l-1] 也就是中间区间 [l,r] 这段的和就出来了

举个例子，a=[1,2,3,4,5]：

s[1]=1, s[2]=3, s[3]=6, s[4]=10, s[5]=15

查询 [2,4] 的和：s[4]-s[1]=10-1=9，即 2+3+4=9

一维差分

接下来是差分。差分就是前缀和的逆运算：前缀和是"前n个累加"，差分是"两两做差"

差分数组，原数组，前缀和数组有一个很特别的关系


            差分               差分
差分数组 <---------- 原数组 <---------- 前缀和数组
        ---------->         ---------->
            前缀和            前缀和

下面便有一个体现两者关系的题目：

输入一个长度为 n的整数序列
接下来输入 m 个操作，每个操作包含三个整数 l, r, c，表示将序列中 [l,r] 之间的每个数加上 c
请你输出进行完所有操作后的序列。

这个题传统的暴力确实可以解，但是时间复杂度就不乐观了，下面来看怎么用差分实现：

#include<iostream>

using namespace std;

const int N= 100010;
int a[N],d[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m;
    cin>> n>> m;
    for(int i=1; i<=n; ++i) cin>> a[i];

//--------------------核心区分割线---------------------
    // 差分数组
    for(int i=1; i<=n; ++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]; // 进行一次前缀和，回到修改后的数组
        cout<< d[i]<<' ';
    }
//--------------------核心区分割线---------------------
    return 0;
}

我们来解释一下核心区域

核心代码

d[i]= a[i]- a[i-1];

这里是差分数组的定义：相邻两个数两两作差，a[i]- a[i-1]

而 差分+前缀和 可以把 "区间修改" 变成 "单点修改"，这也是差分+前缀和的很常见的一个应用：

先对差分数组的如下地方进行操作

d[l] += c;   // 在 l 处加上c
d[r+1] -= c; // 在 r+1 处减去c，在计算前缀和的时候可以防止对 r 位置后的数字造成影响

然后，再进行一次前缀和的操作：

for(int i=1; i<=n; ++i){
    d[i] += d[i-1]; // 进行一次前缀和，回到修改后的数组
    cout<< d[i]<<' ';
}

这样得到的结果就是对特定区间操作后的原数组了，就不用来一次嵌套for循环了

为什么？直接举例子：
a=[a1, a2, a3, a4, a5]，想要给 [a2,a4] 加上c

  • 第一步，得到差分数组
    d=[a1, a2-a1, a3-a2, a4-a3, a5-a4]
  • 第二步d[l] += c; d[r+1] -= c;得到
    d=[a1, a2-a1+c, a3-a2+c, a4-a3+c, a5-a4-c]
  • 最后，按照前缀和操作，最后结果为：
    d=[a1, a2+c, a3+c, a4+c, a5]

二维前缀和

我们先来看一个问题

给出一个点阵，需要你计算某个以 (x1, y1) 为左上角，(x2, y2)为右下角的点阵区域的和

这个问题就是二维前缀和的应用

我们先来给出二维前缀和的几何意义（很重要）：

s[i][j]代表着这个点与坐标原点围成的矩形区域内（包含边界）所有点的权重之和

下面我们来看代码实现：

#include<iostream>
using namespace std;

const int N= 1010;
int a[N][N], s[N][N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin>>n >>m>> q;

    //从 1 开始存可以免去繁杂的边界问题
    for(int i=1;i<=n; ++i){
        for(int j=1; j<=m; ++j){
            cin>>a[i][j];
        }
    }

//--------------------核心区分割线---------------------    
    // 前缀和
    for(int i=1;i<=n; ++i){
        for(int j=1; j<=m; ++j){
            // 注意，这里是点阵，所以是这样计算的（画一个格子点图会更加好理解的😋）
            s[i][j]= s[i-1][j]+ s[i][j-1]+ a[i][j]-s[i-1][j-1];
        }
    }


    // 子矩阵的和
    while(q--){
        // 均为1-base下的索引坐标
        int x1, y1, x2, y2;
        cin>> x1>> y1>> x2>> y2;
        cout<< s[x2][y2]- s[x1-1][y2]- s[x2][y1-1]+ s[x1-1][y1-1]<<'\n';
    }
//--------------------核心区分割线---------------------
    
    return 0;
}

核心代码

前缀和一共有两个公式：

  • s[i][j]= s[i-1][j]+ s[i][j-1]+ a[i][j]-s[i-1][j-1]
  • s[x2][y2]- s[x1-1][y2]- s[x2][y1-1]+ s[x1-1][y1-1]

第一个公式用来计算s[i][j]的值，还记的这个的几何意义吗？s[i][j]代表着这个点与坐标原点围成的区域内（包含边界）所有点的数值之和

第二个公式用来计算以 (x1, y1) 为左上角，(x2, y2)为右下角的点阵区域的和

这两个公式如果自己画一个点阵图，根据s[i][j]的含义就可以很快理解了

差分

说实话，差分这里不方便单独拿出来讲，我觉得配合前缀和一起讲更好
二维差分+前缀和主要解决的是这样一个问题： 给二维点阵某个区域的点全部加上一个数

下面我们来看看代码实现：

#include<iostream>
using namespace std;

const int N= 10010;
int a[N][N], d[N][N];

// 配合前缀和，可以让修改可以形成一个平面范围的影响
// 你可以自己画一个点阵，左上角为原点
// 然后这段代码配合最后的前缀和的几何意义就是：
// 以坐标为左上角的点的矩形，区域内的所有点都加上c
void dif(int x1, int y1, int x2, int y2, int c){
    d[x1][y1]+= c;
    d[x1][y2+1]-= c;
    d[x2+1][y1]-= c;
    d[x2+1][y2+1]+= c;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin>>n >>m>> q;

    // 从 1 开始存可以免去繁杂的边界问题
    for(int i=1;i<=n; ++i){
        for(int j=1; j<=m; ++j){
            cin>>a[i][j];
        }
    }
    
//--------------------核心区分割线---------------------
    // 这里并不是直接采用公式构造，要注意了
    // 这种写法和使用公式构造差分数组的效果是一样的
    // 差分公式：d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]
    for(int i=1;i<=n; ++i){
        for(int j=1; j<=m; ++j){
            dif(i, j, i, j, a[i][j]); 
        }
    }

    // 指定子矩阵区域加上c
    while(q--){
        int x1,y1,x2,y2,c;
        cin>> x1>> y1>> x2>> y2 >>c;
        dif(x1, y1, x2, y2, c);
    }
    for(int i=1;i<=n; ++i){
        for(int j=1; j<=m; ++j){
            d[i][j]+= d[i-1][j]+ d[i][j-1]- d[i-1][j-1]; // 前缀和
        }
    }
//--------------------核心区分割线---------------------
 
    for(int i=1;i<=n; ++i){
        for(int j=1; j<=m; ++j){
            cout<< d[i][j] <<' ';
        }
        cout<<'\n';
    }
}

核心代码

二维差分公式是这个：

  • d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]

但是，这里我们使用了另外一个办法来实现差分数组的创建：

先定义一个dif函数

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

然后这样子写：

// 这里并不是直接采用公式构造，要注意了
    // 这种写法和使用公式构造差分数组的效果是一样的
    for(int i=1;i<=n; ++i){
        for(int j=1; j<=m; ++j){
            dif(i, j, i, j, a[i][j]); 
        }
    }

这样子得到的差分数组和使用公式构造是一个效果的

**可是我们为什么要这样写？**原因：

这个函数配合前缀和，可以让修改可以形成一个平面范围的影响
你可以自己画一个点阵，左上角为原点，然后这段代码配合最后的前缀和的几何意义就是：

以坐标为左上角的点的矩形，区域内的所有点都加上c

这一点很重要，直接影响到我们后续理解，下面这个代码就是对这个意义的应用：

while(q--){
        int x1,y1,x2,y2,c;
        cin>> x1>> y1>> x2>> y2 >>c;
        dif(x1, y1, x2, y2, c);
    }
    for(int i=1;i<=n; ++i){
        for(int j=1; j<=m; ++j){
            d[i][j]+= d[i-1][j]+ d[i][j-1]- d[i-1][j-1]; // 前缀和
        }
    }

还是那句话，可以自己画一个点阵图来理解

评论