二维前缀和和差分

作者: 优劣在于己 | 来源:发表于2020-10-27 21:05 被阅读0次

二维前缀和和差分
Binary Index Tree
前缀和与差分
前缀和差分
差分&&前缀和
差分数组 -- Java版
一些用前缀思想解决的题(持续完善)
Leetcode1109. 航班预订统计
4月
二维前缀和

讲二维之前现得知道什么是前缀和，用例题来了解会更好

题目描述：有个数列a1、a2...an，m 次求任意 [l,r] 的和
没了解过的一般都遍历 l 到 r 的数，然后再累加，时间复杂度为O(n*m);它的数列为10^9，访问次数为10^5,肯定会TLE，前缀和时间复杂度为O(m+n)

前缀和代码：

for(int i=1;i<=n;i++)
   a[i]+=a[i-1];

所以说到底，前缀和就是前面数的总和，这样我们每次只需输出 a[r]-a[l-1]

那什么又是差分？
题目描述：有个数列a1、a2...an，对它进行m次操作，最后询问 [kl,kr] 的和，具体操作如下：
操作1：对区间[a,b]每个元素加p
操作2：对区间[a,b]每个元素减p
看到这题，是否想着对于区间里面的每个数进行加或者减，不用问，数据大了，自然会TLE，所以我们这时候就得用差分了，首先得开个数组ope[]，记录了对这个区间数的操作，代码如下

#include<bits/stdc++.h>
 using namespace std;
int main(){
    int n,m,kl,kr,t,p,a[1000],ope[1000];
    memset(a,0,sizeof a);
    memset(ope,0,sizeof ope);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=0;i<m;i++){//差分
        cin>>t>>kl>>kr>>p;//对[a,b]区间的操作即为[kl,kr]
        if(t==1){
            ope[kl]+=p;
            ope[kr+1]-=p;
        }
        else{
            ope[kl]-=p;
            ope[kr+1]+=p;
        }
    }
    int op=0;
    for(int i=1;i<=n;i++){
        op+=ope[i];
        a[i]+=a[i-1]+op;
    }
    cin>>kl>>kr;
    cout<<a[kr]-a[kl-1]<<endl;
    return 0;
 }

ope[b+1]-=p因为后面的数不进行对p的加，同理加也是
差分也就是一个数组相邻两元素的差，一般为后一位减前一位，上面也就是用这个原理

接下来就是正题啦

首先，二维的前缀和s[][]，如图a[2][3]的前缀和表示的是以下的值

所以求前缀和，如下图 s[2][3]=a[2][3]+s[1][3]+s[2][2]-s[1][2]
就是图中 a[2][3]+(蓝色值)+(紫色值)-(蓝色与紫色重复部分，由于加了2次)
最后可以得出 s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1]

代码：

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];

如若要对区间求和，如下图区间

就可以得到如下图求a[x1,y1]->a[x2][y2]
结果=蓝色部分-黑色两个部分+紫色部分（重复减的）
ans=s[x2][y2]-s[x1-1][y2]-s[x2][y1]+s[x1-1][y1-1]

将前缀和s[][]和a[][]结合一下，代码如下：

#include<iostream>
#include<cstring>
using namespace std;
int a[10005][10005];
int main(){
    int n,m;
    cin>>n>>m;
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];
        }
    }
    int k;
    cin>>k;
    while(k--){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        int ans=a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
        cout<<ans<<endl;
    }
    return 0;
}

同样的如果加上对区间的操作，同一维加上差分即可,再建个数组记录操作
~~差分明天再补充~~（已补充）
该部分来源：https://blog.csdn.net/justidle/article/details/104506724

如果我们要在左上角是 (x1,y1)，右下角是 (x2,y2) 的矩形区间每个值都 +a，如下图所示

在我们要的区间开始位置（x1,y1）处 +c，根据前缀和的性质，那么它影响的就是整个黄色部分，多影响了两个蓝色部分，所以在两个蓝色部分 -c 消除 +c 的影响，而两个蓝色部分重叠的绿色部分多了个 -c 的影响，所以绿色部分 +c 消除影响。所以对应的计算方法如下：

for(int i=0;i<m;i++){//m是修改操作次数 
    int x1,y1,x2,y2,p;
    cin>>x1>>y1>>x2>>y2>>p;
    ope[x1][y1]+=p;
    ope[x1][y2+1]-=p;
    ope[x2+1][y1]-=p;
    ope[x2+1][y2+1]+=p;
}

完整代码如下：

#include <bits/stdc++.h>
using namespace std; 
const int MAXN = 1e3+6;
const int MAXM = 1e3+6;
int a[MAXN][MAXM] = {};
int diff[MAXN][MAXM] = {}; 
int main() {
    int n,m,q;
    cin>>n>>m>>q;
    int i, j;
    for (i=1; i<=n; i++) {
        for (j=1; j<=m; j++) {
            cin>>a[i][j];
            diff[i][j] = a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
        }
    } 
    for (i=0; i<q; i++) {
        int x1, y1, x2, y2, c;
        cin>>x1>>y1>>x2>>x2>>c;
        diff[x1][y1] += c;
        diff[x1][y2+1] -=c;
        diff[x2+1][y1] -=c;
        diff[x2+1][y2+1] += c;
    } 
    for (i=1; i<=n; i++) {
        for (j=1; j<=m; j++) {
            diff[i][j] += diff[i-1][j]+diff[i][j-1]-diff[i-1][j-1];
            cout<<diff[i][j]<<" ";
        }
        cout<<endl;
    } 
    return 0;
}