前缀和与差分图文并茂超级详细整理（全网最通俗易懂）

太过爱你忘了你带给我的痛 2021-07-25 02:40 656阅读 0赞

> 前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和，而差分可以看成前缀和的逆运算。合理的使用前缀和与差分，可以将某些复杂的问题简单化。

### 前缀和： ###

--------------------

![加粗样式][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

## **前缀和算法有什么好处？** ##

**先来了解这样一个问题：**

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

我们很容易想出暴力解法，遍历区间求和。

**代码如下：**

int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    while(m--)
    { 
        int l,r;
        int sum=0;
        scanf("%d%d",&l,&r);
        for(int i=l;i<=r;i++)
        {  
            sum+=a[i];
        }
        printf("%d\n",sum);
    }

这样的时间复杂度为`O(n*m)`，如果`n`和`m`的数据量稍微大一点就有可能超时，而我们如果使用前缀和的方法来做的话就能够将时间复杂度降到`O(n+m)`,大大提高了运算效率。

**具体做法：**

首先做一个预处理，定义一个`sum[]`数组，`sum[i]`代表`a`数组中前`i`个数的和。

**求前缀和运算：**

const int N=1e5+10;
    int sum[N],a[N]; //sum[i]=a[1]+a[2]+a[3].....a[i];
    for(int i=1;i<=n;i++)
    {  
        sum[i]=sum[i-1]+a[i];   
    }

**然后查询操作：**

scanf("%d%d",&l,&r);
     printf("%d\n", sum[r]-sum[l-1]);

对于每次查询，只需执行`sum[r]-sum[l-1]` ，时间复杂度为`O(1)`

**原理**

`sum[r] =a[1]+a[2]+a[3]+a[l-1]+a[l]+a[l+1]......a[r]`;  
`sum[l-1]=a[1]+a[2]+a[3]+a[l-1]`;  
`sum[r]-sum[l-1]=a[l]+a[l+1]+......+a[r]`;

**图解**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]  
这样，对于每个询问，`只需要执行 sum[r]-sum[l-1]`。输出原序列中从第`l`个数到第r个数的和的时间复杂度变成了`O(1)`。

我们把它叫做**一维前缀和**。

**总结：**  
![20201217171740805.png][]  
**练习一道题目**  
输入一个长度为n的整数序列。  
接下来再输入m个询问，每个询问输入一对l, r。  
对于每个询问，输出原序列中从第l个数到第r个数的和。  
**输入格式**  
第一行包含两个整数n和m。  
第二行包含n个整数，表示整数数列。  
接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。  
**输出格式**  
共m行，每行输出一个询问的结果。  
**数据范围**  
1≤l≤r≤n,  
1≤n,m≤100000,  
−1000≤数列中元素的值≤1000  
**输入样例：**  
5 3  
2 1 3 6 4  
1 2  
1 3  
2 4  
**输出样例：**  
3  
6  
10  
**代码：**

#include <iostream>
    
    using namespace std;
    
    const int N = 100010;
    
    int n, m;
    int a[N], s[N];
    
    int main()
    { 
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    
        for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; // 前缀和的初始化
    
        while (m -- )
        { 
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", s[r] - s[l - 1]); // 区间和的计算
        }
    
        return 0;
    }

## 二维前缀和 ##

**如果数组变成了二维数组怎么办呢？**

**先给出问题：**

输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。

同一维前缀和一样，我们先来定义一个二维数组`s[][]`, `s[i][j]`表示二维数组中，左上角`(1,1)`到右下角`( i,j )`所包围的矩阵元素的和。接下来推导二维前缀和的公式。

先看一张图：

![20201214201734653.png][]

**紫色面积**是指`(1,1)`左上角到`(i,j-1)`右下角的矩形面积, **绿色面积**是指`(1,1)`左上角到`(i-1, j )`右下角的矩形面积。**每一个颜色的矩形面积都代表了它所包围元素的和。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 2]  
**从图中我们很容易看出**，整个外围蓝色矩形面积`s[i][j]` = 绿色面积`s[i-1][j]` \+ 紫色面积`s[i][j-1]` \- 重复加的红色的面积`s[i-1][j-1]`\+小方块的面积`a[i][j]`;

**因此得出二维前缀和预处理公式**

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

**接下来回归问题**去求以`(x1,y1)`为左上角和以`(x2,y2)`为右下角的矩阵的元素的和。

**如图：**  
![20201214204543274.png][]

**紫色面积**是指 `( 1,1 )`左上角到`(x1-1,y2)`右下角的矩形面积 ，**黄色面积**是指`(1,1)`左上角到`(x2,y1-1)`右下角的矩形面积；

**不难推出：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 3]

绿色矩形的面积 = 整个外围面积`s[x2, y2]` \- 黄色面积`s[x2, y1 - 1]` \- 紫色面积`s[x1 - 1, y2]` \+ 重复减去的红色面积 `s[x1 - 1, y1 - 1]`

**因此二维前缀和的结论为：**

以`(x1, y1)`为左上角，`(x2, y2)`为右下角的子矩阵的和为：  
`s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]`

**总结：**

![2020121717185394.png][]

**练习一道完整题目：**  
输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

**输入格式**  
第一行包含三个整数n，m，q。

接下来n行，每行包含m个整数，表示整数矩阵。

接下来q行，每行包含四个整数x1, y1, x2, y2，表示一组询问。

**输出格式**  
共q行，每行输出一个询问的结果。

**数据范围**  
1≤n,m≤1000,  
1≤q≤200000,  
1≤x1≤x2≤n,  
1≤y1≤y2≤m,  
−1000≤矩阵内元素的值≤1000  
**输入样例：**  
3 4 3  
1 7 2 4  
3 6 2 8  
2 1 2 3  
1 1 2 2  
2 1 3 4  
1 3 3 4  
**输出样例：**  
17  
27  
21

**代码：**

#include<iostream>
    #include<cstdio>
    using namespace std;
    const int N=1010;
    int a[N][N],s[N][N];
    int main()
    { 
        int n,m,q;
        scanf("%d%d%d",&n,&m,&q);
        for(int i=1;i<=n;i++)
          for(int j=1;j<=m;j++)
           scanf("%d",&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--)
        { 
            int x1,y1,x2,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            printf("%d\n",s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);
        }
        return 0;
    }

## 差分 ##

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 4]

## 一维差分 ##

类似于数学中的求导和积分，**差分可以看成前缀和的逆运算。**

**差分数组：**

首先给定一个原数组`a`：`a[1], a[2], a[3],,,,,, a[n];`

然后我们构造一个数组`b` ： `b[1] ,b[2] , b[3],,,,,, b[i];`

使得 `a[i] = b[1] + b[2 ]+ b[3] +,,,,,, + b[i]`

也就是说，`a`数组是`b`数组的前缀和数组，反过来我们把`b`数组叫做`a`数组的**差分数组**。换句话说，每一个`a[i]`都是`b`数组中从头开始的一段区间和。

考虑如何构造差分`b`数组？

最为直接的方法

**如下：**

`a[0 ]= 0;`

`b[1] = a[1] - a[0]`;

`b[2] = a[2] - a[1]`;

`b[3] =a [3] - a[2]`;

`........`

`b[n] = a[n] - a[n-1]`;

**图示:**  
![20201215214337143.png][]

我们只要有`b`数组，通过前缀和运算，就可以在`O(n)` 的时间内得到`a`数组 。

**知道了差分数组有什么用呢？** 别着急，慢慢往下看。

**话说有这么一个问题：**

给定区间`[l ,r ]`，让我们把`a`数组中的`[ l, r]`区间中的每一个数都加上`c`,即 `a[l] + c , a[l+1] + c , a[l+2] + c ,,,,,, a[r] + c`;

暴力做法是`for`循环`l`到`r`区间，时间复杂度`O(n)`，如果我们需要对原数组执行`m`次这样的操作，时间复杂度就会变成`O(n*m)`。有没有更高效的做法吗? **考虑差分做法**，(差分数组派上用场了)。

**始终要记得，a数组是b数组的前缀和数组**，比如对`b`数组的`b[i]`的修改，会影响到`a`数组中从`a[i]`及往后的每一个数。

首先让差分`b`数组中的 `b[l] + c` ,通过前缀和运算，`a`数组变成 `a[l] + c ,a[l+1] + c,,,,,, a[n] + c`;

然后我们打个补丁，`b[r+1] - c`, 通过前缀和运算，`a`数组变成 `a[r+1] - c,a[r+2] - c,,,,,,,a[n] - c`;

**为啥还要打个补丁？**

**我们画个图理解一下这个公式的由来:**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 5]  
`b[l] + c`，效果使得`a`数组中 `a[l]`及以后的数都加上了`c`(红色部分)，但我们只要求`l`到`r`区间加上`c`, 因此还需要执行 `b[r+1] - c`,让`a`数组中`a[r+1]`及往后的区间再减去`c`(绿色部分)，这样对于`a[r]` 以后区间的数相当于没有发生改变。

因此我们得出**一维差分结论**：给`a`数组中的`[ l, r]`区间中的每一个数都加上`c`,只需对差分数组`b`做 `b[l] + = c`, `b[r+1] - = c`。时间复杂度为`O(1)`, 大大提高了效率。

**总结：**  
![在这里插入图片描述][20201217172005485.png]

**题目练习：** **AcWing 797. 差分**

输入一个长度为n的整数序列。  
接下来输入m个操作，每个操作包含三个整数l, r, c，表示将序列中\[l, r\]之间的每个数加上c。  
请你输出进行完所有操作后的序列。  
**输入格式**  
第一行包含两个整数n和m。  
第二行包含n个整数，表示整数序列。  
接下来m行，每行包含三个整数l，r，c，表示一个操作。  
**输出格式**  
共一行，包含n个整数，表示最终序列。  
**数据范围**  
1≤n,m≤100000,  
1≤l≤r≤n,  
−1000≤c≤1000,  
−1000≤整数序列中元素的值≤1000  
**输入样例：**  
6 3  
1 2 2 1 2 1  
1 3 1  
3 5 1  
1 6 1  
**输出样例：**  
3 4 5 3 4 2  
**AC代码**

//差分 时间复杂度 o(m)
    #include<iostream>
    using namespace std;
    const int N=1e5+10;
    int a[N],b[N]; 
    int main()
    { 
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) 
        { 
            scanf("%d",&a[i]);
            b[i]=a[i]-a[i-1];      //构建差分数组
        }
        int l,r,c;
        while(m--)
        { 
            scanf("%d%d%d",&l,&r,&c);
            b[l]+=c;     //表示将序列中[l, r]之间的每个数加上c
            b[r+1]-=c;
        }
        for(int i=1;i<=n;i++) 
        { 
            b[i]+=b[i-1];  //求前缀和运算
            printf("%d ",b[i]);
        }
        return 0;
    }

## 二维差分 ##

如果扩展到二维，我们需要让二维数组被选中的子矩阵中的每个元素的值加上`c`,是否也可以达到`O(1)`的时间复杂度。答案是可以的，**考虑二维差分**。

`a[][]`数组是`b[][]`数组的前缀和数组，那么`b[][]`是`a[][]`的差分数组

原数组： `a[i][j]`

我们去构造差分数组： `b[i][j]`

使得`a`数组中`a[i][j]`是`b`数组左上角`(1,1)`到右下角`(i,j)`所包围矩形元素的和。

**如何构造`b`数组呢？**

其实关于差分数组，我们并不用考虑其构造方法，因为我们使用差分操作在对原数组进行修改的过程中，实际上就可以构造出差分数组。

同一维差分，我们构造二维差分数组目的是为了 让原二维数组`a`中所选中子矩阵中的每一个元素加上`c`的操作，可以由`O(n*n)`的时间复杂度优化成`O(1)`

已知原数组`a`中被选中的子矩阵为 以`(x1,y1)`为左上角，以`(x2,y2)`为右上角所围成的矩形区域;

**始终要记得，a数组是b数组的前缀和数组**，比如对`b`数组的`b[i][j]`的修改，会影响到`a`数组中从`a[i][j]`及往后的每一个数。

假定我们已经构造好了`b`数组，类比一维差分，我们执行以下操作  
来使被选中的子矩阵中的每个元素的值加上`c`

`b[x1][y1] + = c`;

`b[x1,][y2+1] - = c`;

`b[x2+1][y1] - = c`;

`b[x2+1][y2+1] + = c`;

每次对`b`数组执行以上操作，**等价于：**

for(int i=x1;i<=x2;i++)
      for(int j=y1;j<=y2;j++)
        a[i][j]+=c;

**我们画个图去理解一下这个过程：**

![20201217171134926.png][]

`b[x1][ y1 ] +=c` ; 对应图1 ,让整个`a`数组中**蓝色矩形面积**的元素都加上了`c`。  
`b[x1,][y2+1]-=c` ; 对应图2 ,让整个`a`数组中**绿色矩形面积**的元素再减去`c`，使其内元素不发生改变。  
`b[x2+1][y1]- =c` ; 对应图3 ,让整个`a`数组中**紫色矩形面积**的元素再减去`c`，使其内元素不发生改变。  
`b[x2+1][y2+1]+=c`; 对应图4,让整个`a`数组中**红色矩形面积**的元素再加上`c`，红色内的相当于**被减了两次**，再加上一次`c`，才能使其恢复。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 6]  
**我们将上述操作封装成一个插入函数:**

void insert(int x1,int y1,int x2,int y2,int c)
    {      //对b数组执行插入操作，等价于对a数组中的(x1,y1)到(x2,y2)之间的元素都加上了c
        b[x1][y1]+=c;
        b[x2+1][y1]-=c;
        b[x1][y2+1]-=c;
        b[x2+1][y2+1]+=c;
    }

我们可以先假想`a`数组为空，那么`b`数组一开始也为空，但是实际上`a`数组并不为空，因此我们每次让以`(i,j)`为左上角到以`(i,j)`为右上角面积内元素(其实就是一个小方格的面积)去插入 `c=a[i][j]`，等价于原数组`a`中`(i,j)` 到`(i,j)`范围内 加上了 `a[i][j]` ,因此执行`n*m`次插入操作，就成功构建了差分`b`数组.

**这叫做曲线救国。**

**代码如下：**

for(int i=1;i<=n;i++)
      { 
          for(int j=1;j<=m;j++)
          { 
              insert(i,j,i,j,a[i][j]);    //构建差分数组
          }
      }

当然关于二维差分操作也有直接的构造方法，**公式如下：**

`b[i][j]=a[i][j]−a[i−1][j]−a[i][j−1]+a[i−1][j−1]`

二维差分数组的构造同一维差分思维相同，因次在这里就不再展开叙述了。

**总结：**

![在这里插入图片描述][20201217172035975.png]

**题目练习：** **AcWing 798. 差分矩阵**  
输入一个n行m列的整数矩阵，再输入q个操作，每个操作包含五个整数x1, y1, x2, y2, c，其中(x1, y1)和(x2, y2)表示一个子矩阵的左上角坐标和右下角坐标。  
每个操作都要将选中的子矩阵中的每个元素的值加上c。  
请你将进行完所有操作后的矩阵输出。  
**输入格式**  
第一行包含整数n,m,q。  
接下来n行，每行包含m个整数，表示整数矩阵。  
接下来q行，每行包含5个整数x1, y1, x2, y2, c，表示一个操作。  
**输出格式**  
共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。  
**数据范围**  
1≤n,m≤1000,  
1≤q≤100000,  
1≤x1≤x2≤n,  
1≤y1≤y2≤m,  
−1000≤c≤1000,  
−1000≤矩阵内元素的值≤1000  
**输入样例：**  
3 4 3  
1 2 2 1  
3 2 2 1  
1 1 1 1  
1 1 2 2 1  
1 3 2 3 2  
3 1 3 4 1  
**输出样例：**  
2 3 4 1  
4 3 4 1  
2 2 2 2  
**AC代码：**

include<iostream>
    #include<cstdio>
    using namespace std;
    const int N=1e3+10;
    int a[N][N],b[N][N];
    void insert(int x1,int y1,int x2,int y2,int c)
    { 
        b[x1][y1]+=c;
        b[x2+1][y1]-=c;
        b[x1][y2+1]-=c;
        b[x2+1][y2+1]+=c;
    }
    int main()
    { 
      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];
      for(int i=1;i<=n;i++)
      { 
          for(int j=1;j<=m;j++)
          { 
              insert(i,j,i,j,a[i][j]);    //构建差分数组
          }
      }
      while(q--)
      { 
          int x1,y1,x2,y2,c;
          cin>>x1>>y1>>x2>>y2>>c;
          insert(x1,y1,x2,y2,c);
      }
      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];
          }
      }
      for(int i=1;i<=n;i++)
      { 
          for(int j=1;j<=m;j++)
          { 
              printf("%d ",b[i][j]);
          }
          printf("\n");
      }
      return 0;
    }

如果我的文章对你有帮助，请点点关注，你的关注是对我创作的最大支持。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 7]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/04257db1adaa456999daa1ba2d2b4ef0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]: /images/20210724/99a715da452743d9ab5a1e9b3c513ee8.png
[20201217171740805.png]: /images/20210724/ddc0631c34594b4d9f6edfd70d43582c.png
[20201214201734653.png]: /images/20210724/2148706e3a7d4e80a68b7c8fc5e227ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 2]: /images/20210724/c85a0515426140eb9918f3eb09abd877.png
[20201214204543274.png]: /images/20210724/22d9e98ca5f34e2bb043293517ac5cb0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 3]: /images/20210724/3c8a0e587b89436d84d6c64bf4d5d7ad.png
[2020121717185394.png]: /images/20210724/5f36b5cea4ba4821bbd61df4de8b59cf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 4]: /images/20210724/a65ce229e2304f0db3e1eb668efae0b3.png
[20201215214337143.png]: /images/20210724/29d87cacec87478e808c84c6fc07f1c4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 5]: /images/20210724/b7dc21a567bf4895ab4bf44339dacdbf.png
[20201217172005485.png]: /images/20210724/32b91c3179a74f52ad156c073646283d.png
[20201217171134926.png]: /images/20210724/0d7696afeda54c14a7be335e6a384e6d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 6]: /images/20210724/84f65e0d2c8e492880fe7f4083e1d1f8.png
[20201217172035975.png]: /images/20210724/89e9ad592acc4698ba269ded06b31f9d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 7]: /images/20210724/b235180fa3df4d9abaaf9e054d5d48b3.png