前缀和与差分

一维前缀和

e.g. 给定长度为n的数组arr, 求q次询问中每次arr在[l,r]的区间和

暴力枚举的时间复杂度为O(qn) 容易TLE

使用前缀和可以极大减少运行时间

前缀和数组

定义一个前缀和数组prefix[i]=prefix[i-1]+arr[i]，其中i>0

i=0时sum[0]=arr[0]

则对于数a1,a2,a3,a4,a5….

prefix[1]=a1

prefix[2]=a1+a2

prefix[3]=a1+a2+a3

…

可以看出，prefix[i]为区间[0,i]的和

在求区间的和时，如2-4，就可以使用prefix[4]-prefix[1],通式为prefix[r]-prefix[l-1], l=0时为prefix[r]

其中，求前缀和的过程成为预处理

板子

#include <iostream>
//#define get_sum(l, r) ((l)?(sum[r]-sum[l]):(sum[r]))
using namespace std;
const int N = 10000;
int a[N], prefix[10000];
int get_sum(int l , int r){
    if (l) return prefix[r]-prefix[l-1];
    else return prefix[r];
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <=n ; i++)
    {
        cin >> a[i];
    }
    // 预处理，一般以1开始为下标
    for (int i = 1; i <= n; i++)
    {
        prefix[i] = prefix[i-1]+a[i];
    }
    // 访问
    int q;
    cin >> q;
    while (q--){
        int l, r ;
        cin >> l >> r;
        //cout << prefix[r]-prefix[l-1];
        cout << get_sum(l,r);
    }
    return 0;
}

二维前缀和

给定一个长n,宽m的矩阵:

求矩阵任意两点间矩形的数字之和

二维前缀和数组

定义一个二维前缀和数组prefix[i][j] =prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+a[i][j]，其中i>0

其中，prefix[i][j]为从(0,0)到(i,j)的和

当i=0且j=0时，prefix[0][0]=a[0][0]
当i=0且j!=0时，prefix[0][j]=prefix[0][j-i]+a[0][j]
当i!=0且j=0时，prefix[i][0]=prefix[i-1][0]+a[i][0]

如下图：

即prefix[i][j]是由a[i][j],prefix[i-1][j],prefix[i][j-1]组成的，但两块加多了一块prefix[i-1][j-1]，故减去

若要求解某部分矩形，就可以进行以上的逆过程

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

从prefix[i][j]开始，求a[i][j]，则可以依次减去prefix[i-1][j],prefix[i][j-1]，但会多减一块prefix[i-1][j-1]，故加上

板子

#include <iostream>
using namespace std;
const int N = 10000;
int n,m;
int a[N][N];
int prefix[N][N];
void pre_sum(){
  /*以下代码是当for循环从0开始时的初始化
  prefix[0][0]=a[0][0];
  for (int i = 1;i <n;i++) prefix[i][0] = prefix[i-1][0]+a[i][0];
  for (int j = 1;j <m;j++) prefix[0][j] = prefix[0][j-1]+a[0][j];
  */
 for (int i = 1;i<=n;i++){
  for (int j = 1;j<=m;j++){
    prefix[i][j] = prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+a[i][j];
  }
 }
}
int get_sum(int x1, int y1, int x2, int y2){
  /*以下为从0开始时的特殊情况
  // 从0,0开始加
  if (!x1 && !y1) return prefix[x2][y2];
  // 成行相加
  if (!x1) return prefix[x2][y2]-prefix[x2][y1-1];
  // 成列相加
  if (!y1) return prefix[x2][y2]-prefix[x1-1][y2];
  */
  return prefix[x2][y2]-prefix[x1-1][y2]-prefix[x2][y1-1]+prefix[x1-1][y1-1];

}
int main(){
  int x1,y1,x2,y2;
  cin >> n >>m;
  for (int i = 1; i <=n; i++){
    for (int j = 1;j <=m; j++){
      cin >> a[i][j];
    }
  }
  cin >> x1 >> y1 >> x2 >> y2;
  pre_sum();
  cout << get_sum(x1,y1,x2,y2);
  return 0;

}

一维差分

给定长度为n的数组arr，进行m个操作，使[l,r]区间内的值都加一个value，操作结束后，询问arr

暴力解法：每次遍历数组[l,r]执行加value操作，遍历m次，时间复杂度O(n*m)

例如 arr中有五个数 1 3 7 5 2

对[2,4] +5 [1,3] +2 [0,2] -3

对于下标为2的数分析，7+5+2-3=11. 若不管中间，则相当于7+4=11. 则我们的目的即为让中间的步骤省略，最后只+4.

差分数组

定义一个差分数组d[i]=arr[i]-arr[i-1]

则对d进行前缀和，得到前缀和数组sum，我们可以发现：

差分数组可以通过前缀和得到原数组

即d[i]+=d[i-1]

差分标记

对于一位差分区间修改：[l,r]+value\(\iff\)d[l]+value, d[r+1]-value

对于以上arr 对应差分数组d为1 2 4 -2 -3

第一次操作等价于d[2]+5 结果为1 2 9 -2 -3

第二次等价于d[1]+2,d[4]-2 结果为1 4 9 -2 -5

第三次：-2 4 9 1 -5

进行前缀和得到sum -2 2 11 12 7

注意：

把标记后的差分数组进行一次前缀和操作
每进行m次操作后都要进行一次前缀和
即适用于多次操作单次询问（单次操作单次询问不适用）

原理： 差分数组中，标记位加了一个数，还原成原数组的时候，后面的数都会累加，然后再r+1位在减去这个数停止累加

最终实现的效果为：sum[l,r]+value, sum[r+1,n-1] +value - value

如：对于差分数组d 0 1 0 0 0，进行一次前缀和后其sum为 0 1 1 1 1，即标记位加的数会作用与该标记之后每一位，即d[i]+value \(\iff\) sum[i,n-1]+value

若想在某位置停止累加，在该位置+1处减掉value即可，如 d 0 1 0 0 -1，前缀和后sum为 0 1 1 1 0，加一减一抵消为0，即d[r+1]-value \(\iff\) sum[r+1,n-1]-value

板子

#include <iostream>
using namespace std;
int main(){
    int a[10000]={0}, diff[10000]={0}, prefix[10000]={0};
    int n;
    cin >> n;
    for (int i = 1; i <=n ; i++)
    {
        cin >> a[i];
    }
    // 预处理，得到差分数组，一般以1开始为下标
    for (int i = 1; i <= n; i++)
    {
        diff[i] = a[i]-a[i-1];
    }
    // 对区间元素处理
    // 想让区间元素都+x，则可以让l右边都加x，再r右边都-x
    int m;
    cin >> m;
    while(m--){
        int l, r, x;
        cin >> l>> r>> x;
        // 进行差分标记
        diff[l]+=x, diff[r+1]-=x;
    }
    // 对差分数组进行前缀和得出结果
    for (int i = 1; i <=n; i++)
    {
        a[i] = a[i-1] +diff[i];
    }
    // 再进行前缀和以应对接下来的访问
    for (int i = 1; i <= n; i++)
    {
        prefix[i] = prefix[i-1]+a[i];
    }
    // 访问
    int q;
    cin >> q;
    while (q--){
        int l, r ;
        cin >> l >> r;
        cout << prefix[r]-prefix[l-1];
    }
    return 0;
}

二维差分

给定长n,宽m的矩阵，从(xi,yi)到(xj,yj)执行m次操作，使两点间矩形中的值都加一个value，操作结束后，询问矩阵

大体思路与一维差分差不多

差分矩阵

定义一个差分矩阵：d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]

或者可以将差分矩阵中的元素一个个插入：

即若原矩阵(x,y)处值为value，则相当于从左上角(x,y) 到右下角(x,y)都加value,也可以使用差分标记实现

差分标记

对于二位差分区间修改：[(xi,yi),(xj,yj)]+value\(\iff\)d[xi][yi]+value, d[xj+1][yi]-value, d[xi][yj+1]-value, d[xj+1][yj+1]+value

原理如图：

板子

#include <iostream>
using namespace std;
const int N = 10000;
int n,m,cnt=0;
int a[N][N];
int prefix[N][N];
int d[N][N];

// 差分标记 &&初始化差分矩阵
void add(int x1, int y1, int x2, int y2,int value){
  d[x1][y1]+=value;
  d[x2+1][y1]-=value;
  d[x1][y2+1]-=value;
  d[x2+1][y2+1]+=value;
}
int main(){
  
  cin >> n >>m >> cnt;
  // 输入每个数并计算差分矩阵
  for (int i = 1; i <=n; i++){
    for (int j = 1;j <=m; j++){
      cin >> a[i][j];
      add(i,j,i,j,a[i][j]);
    }
  }
  // 进行差分标记
  for (int i = 1; i <=cnt;i++){
    int x1,y1,x2,y2,value;
    cin >> x1 >> y1 >> x2 >> y2>>value;
    add(x1,y1,x2,y2,value);
  }
  // 对差分数组进行一次前缀和得到结果
  for (int i = 1 ;i <=n;i++){
    for (int j = 1;j <=m;j++){
      a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + d[i][j];
    }
  }
  for (int i = 1;i <= n; i++){
    for (int j = 1; j <= m; j++){
      cout << a[i][j] << ' ';
    }
    cout << endl;
  }
  return 0;

}

红魔咖啡馆

【算法】前缀和与差分

前缀和与差分

一维前缀和

前缀和数组

板子

二维前缀和

二维前缀和数组

板子

一维差分

差分数组

差分标记

板子

二维差分

差分矩阵

差分标记

板子