c++灵活实现前缀和与差分

前缀和与差分

1.一维前缀和

注意

1. 前缀和下标要从1开始，因为边界S0要定义成0。

2. 作用：可以快速求出某个数组区间内的和。

   #include<bits/stdc++.h>
   using namespace std;
   const int N = 1e5 + 10;
   int s[N],a[N];//全局变量默认为0
   int main()
   {
       int m,n;
       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];
       while(m--)
       {
           int l,r;
           cin>>l>>r;
           cout<<s[r]-s[l-1]<<endl;
       }
       return 0;
   }
   

2.二维前缀和

前缀和公式：s [i] [j] = s [i-1] [j] + s [i] [j-1] - s [i-1] [j-1] + a [i] [j]

部分和公式：s [x2] [y2] - s [x2] [y1-1] - s [x1-1] [y2] + s [x1-1] [y1-1]

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N][N],s[N][N];
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++) s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];//计算前缀和
        
    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]<<endl;//计算部分和
    }
    return 0;
}

3.一维差分

给某一个区间加一个值或减去一个值

注意：因为A数组是B数组的前缀和，所以：b[l]+c等价于a[l]+c，a[l+1]+c…a[n]+c。

开始把前缀和数组看成0，所以差分数组也是0，然后经过n步加值操作到差分数组，再求前缀和就是操作后的数组。

在某个区间的每一个数加上某个值等价于在他的差分数组的区间边界加上这个值==》前缀和和差分第一个数不会变！！！

求差分数组也可以用b[i] = a[i]-a[i-1]!!!这个好理解一些

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

void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        insert(i,i,a[i]);//重点理解==》差分（上面提到的加值操作）
    }
    
    while(m--)
    {
        int l,r,c;
        cin>>l>>r>>c;
        insert(l,r,c);
    }
    
    for(int i=1;i<=n;i++)
    {
        b[i]+=b[i-1];
        cout<<b[i]<<' ';
    }
    return 0;
}

例：

Acwing__100题：增减序列（很强的差分思想）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=n;i>1;i--) a[i] -= a[i-1];
    
    LL zh=0,fu=0;
    for(int i=2;i<=n;i++)//把差分数组的2~n项全部变成零，每次选一个正数一个负数。所以记录正数和负数的个数即可。
        if(a[i]>0) zh+=a[i];
        else fu-=a[i];
    cout<<max(zh,fu)<<endl<<abs(zh-fu) + 1;//差分数组剩余的和a[n+1](因为a[n+1]在所求数组范围外，不影响原数组变化)换或者和a[1]换，所以有最后剩余的加一种。
    return 0;
}

4.二维差分

某一个子矩阵内的值加一个值或者减去一个值

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N][N];
//int 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;
    
    a[x1][y1] += c;
    a[x2+1][y1] -= c;
    a[x1][y2+1] -= c;
    a[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];
            //insert(i,j,i,j,a[i][j]);//方法二求差分数组（要开两个数组）
        }
        
    for(int i=n;i>=1;i--)
        for(int j=m;j>=1;j--) a[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1];//方法一求差分数组（只需要开一个数组）
        
    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++) 
        {
            a[i][j] = a[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
            cout<<a[i][j]<<' ';
        }
        cout<<endl;
    }
        return 0;
}
    
    

差分步骤

1. 先求出差分数组
2. 对差分数组进行加减
3. 对操作后的差分数组求前缀和