推荐软件产品
twitter,facebook,ins,youtube视频下载
磨针音视频转文字
磨针免费pdf转word
磨针微信定时发文件和消息
磨针c盘清理，任何场景都能释放几十G的空间

1. 前缀和

1.1 算法原理

所谓前缀和，就是记录下前方所有数据之和，当所需中间数据时，可以通过o(1)的时间复杂度将数据求出。

一维数组前缀和

求出1~i的所有项之和。

由于当运算到第i位时，前i-1位已经运算完成，故a[i] = a[i] + a[i-1]。

当需要[l,r]之和时，可以通过a[r]-a[l-1]求出

二维数组前缀和

求出左上端点、右下端点分别为(1,1)，(i,j)的长方形内的数据之和

当运算到(i,j)时，前i-1排、第i排前j-1位均已运算完成，故a[i][j] = a[i][j]+a[i-1][j]+a[i-1]-a[i-1][j-1]。

当需要左上端点、右下端点分别为(x1,y1)，(x2,y2)的长方形内的数据之和时，a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1]

1.2 例题

参考代码：

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
    while(m--){
        cin>>l>>r;
        cout<<a[r]-a[l-1]<<endl;
    }
}

参考代码：

void solve(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
        cin>>a[i][j],a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
    while(q--){
        cin>>x1>>y1>>x2>>y2;
        cout<<a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1]<<endl;
    }
}

2.1 算法原理2. 差分

所谓差分，就是记录每位数据与前一位数据之间的差，当需要对区间进行操作时，可以通过o(1)的时间复杂度完成操作。

同时我们可以发现差分数组的前缀和就是原数组。

一维数组差分

求出与前一项之差。

当需要对[l,r]范围内的数进行加减操作时时，可以通过b[l]+c、b[r+1]-c实现

二维数组差分

二维差分数组的构建可以由其前缀和的结果来逆向考虑。

当对(x1,y1)，(x2,y2)的长方形内的数据都加上c时，即a[x1,y1]~a[x2,y2]均加c。故当b[x1,y1]+=c，b[x1,y2+1]-=c，b[x2+1,y1]-=c，b[x2+1,y2+1]+=c，即可实现仅区间内的数据加c。

当构建差分数组时，可以发现其为对长宽为1的长方形加a[i,j]，由此实现二维差分数组。

2.2 例题

void solve(){
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) b[i] = a[i]-a[i-1];
    while(m--){
        cin>>l>>r>>c;
        b[l]+=c;b[r+1]-=c;
    }for(int i=1,t=0;i<=n;i++) t+=b[i],cout<<t<<' '; 
}

void add(){
    b[x1][y1] += c;b[x1][y2+1] -=c;
    b[x2+1][y1] -= c;b[x2+1][y2+1] +=c;
}
void solve(){
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
        cin>>a[i][j],x1=x2=i,y1=y2=j,c=a[i][j],add();
    while(q--){
        cin>>x1>>y1>>x2>>y2>>c;
        add();
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j] = b[i][j] + a[i-1][j]+a[i][j-1]-a[i-1][j-1];
            cout<<a[i][j]<<' ';
        }cout<<endl;
    }
}