简单复习下前缀和差分

SparkKnight · 2023-06-17 18:19:19 · 个人记录

前缀和、差分，很好理解吧？

前缀和就是数组里的每一个数都和前面的加在一起，差分就是把变化量另外计一个数组，和原始数组一加就是真实数据。

但差分还有一个优势，那就是和前缀和相结合：这样批量修改数据只需要修改差分数组里的两个数据，然后一块求前缀和即可：

//T313539 【模板】差分
#include <bits/stdc++.h>
using namespace std;
int n,m,*C,*sum;
int main()
{
    cin>>n>>m;
    C=new int[n+2];
    sum=new int[n+2];
    for(int i=0;i<=n+1;i++){sum[i]=0;}
    for(int i=1;i<=n;i++){cin>>C[i];}
    for(int i=1,l,r,c;i<=m;i++)
    {
        cin>>l>>r>>c;
        sum[l]+=c;
        sum[r+1]-=c;
    }
    for(int i=1;i<=n;i++)
    {
        sum[i]+=sum[i-1];
    }
    for(int i=1;i<=n;i++)
    {
        cout<<C[i]+sum[i]<<" ";
    }
    return 0;
}

但它最难的地方，还是它的二维版本。这里当然可以用几何法现推，而我选择直接记公式：

//求矩阵前缀和
sumMap[i][j]=sumMap[i-1][j]+sumMap[i][j-1]-sumMap[i-1][j-1]+ikun;
//求矩阵（x1,y1,x2,y2）内数字和：
sumMap[x2][y2]-sumMap[x1-1][y2]-sumMap[x2][y1-1]+sumMap[x1-1][y1-1]
//将矩阵（x1,y1,x2,y2）内增加c（差分）：
cf[x1][y1]+=c;
cf[x2+1][y2+1]+=c;
cf[x1][y2+1]-=c;
cf[x2+1][y1]-=c;

用时往里套就行了。