前缀和与差分

一维前缀和

算法思想

1.数组从a1，a2...a存储，前缀和的定义为S_i=a₁+a₂+...+a_i\ 2.求S_i\ 设置S₀ = 0.通过循环，S_i = S_i-1+a_i，即可求出每个S_i的值 3.求区间[l,r]的值x\ 利用x = S_i-S_i-1，即可求出答案。

完整代码

#include<iostream>
using namespace std;
const int N = 1e6 +10;
int n,m;
int q[N],S[N];

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++) scanf("%d",&q[i]);
    S[0] = 0;
    for(int i = 1;i <= n;i ++) S[i] = S[i-1] + q[i];            //前缀和的初始化
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d",S[r] - S[l - 1]);                   //区间和的计算
    }
    return 0;
}

二维前缀和

算法思想

1.数组存储在二位数组中 前缀和为S_ij，即包含在这个面积里面数的总和\ 2.求S_ij\ 计算公式S_ij = S_i-1j + S_ij-1 + a_ij;初始化S[0][0] = 0,通过2层for循环即可求出S[i][j]的值。 3.求子矩阵(x1,y1)到(x2,y2)的值x\ x = S[x2][y2] - S[x1 - 1][y2]-S[x2][y1 - 1] + S[x1 - 1][y1 - 1]

完整代码

#include<iostream>
using namespace std;
const int N = 1010;
int n,m,q;
int a[N][N],S[N][N];

int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            S[0][0] = 0;
            S[i][j] = S[i - 1][j] + S[i][j - 1] + a[i][j];          //求前缀和
        }
    }
    while(q--){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",S[x2][y2]-S[x1 - 1][y2]-S[x2][y1 - 1] + S[x1 - 1][y1 - 1]);   //算子矩阵的和

    }
    return 0;
}

一维差分(前缀和的逆运算)

算法思想

1.数组a[1],a[2]...a[n]，构造数组b[1],b[2]...b[n]使得a[i] = b[1] + b[2] + ... +b[i] 此时a为b的前缀和，b为a的差分。

2.要让a[l]到a[r]中的每个数都+c也就是a[l] + c,a[l + 1] + c,…,a[r] + c
3.那么当b[l] + c时，a[l]至a[r]都会+c，并且a[r+1]到a[n]都会+c。
为了使a[r+1]到a[n]不能+c，则令b[r + 1] - c,即可做到。
※数据初始化时，令数组a与数组b中的元素都是0，然后再利用上面的性质，也就是数组b在[i,i]中插入要输入的数值a[i]，这样就完成了数组b的初始化过程。所以要设一个insert插入函数，在[l，r]中插入数据c，也就是b[l] += c,b[r + 1] -= c。

完整代码

//一维差分
#include<iostream>
using namespace std;

int n,m;
const int N = 1e6 +10;
int a[N],b[N];

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

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
    for(int i = 1;i <= n;i ++) insert(i,i,a[i]);        //相当于在初始化数组
    while(m--){
        int l,r,c;
        scanf("%d%d%d",&l,&r,&c);
        insert(l,r,c);
    }
    for(int i = 1;i <= n;i ++) b[i] += b[i - 1];
    for(int i = 1;i <= n;i ++) printf("%d\t",b[i]);
    return 0;
}

提示

1.最开始时就假设了数组a与数组b中的元素都为0，也就是满足了上述数组a与数组b的关系

2.然后为了改变数组a中的值也就是改变数组b的值，也就是用插入函数改变b数组元素的值，最后求b数组的前缀和也就是求出了a数组。

二维差分

算法思想

1.与一维差分相似，初始时数组a与数组b中的元素值全为0，即构造出了符合数组a与数组b关系的数组
2.书写更新b数组的inert()函数,假设在[x1,y1][x2,y2]的子矩阵中的每个元素都+c
则更新的函数insert()函数为:
b[x1][y1] +=c
b[x2 + 1][y1] -= c
b[x1][y2 + 1] -= c
b[x2 + 1][y2 + 1] += c
3.然后就是接收a数组元素的值，然后根据a数组改变b数组的值，利用insert()函数改变
4.最后求出b数组的前缀和也就是要求的答案了.

完整代码

#include<iostream>
using namespace std;
const int N = 1010;
int a[N][N];
int b[N][N];
int n,m,p;

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;
}
int main(){
    scanf("%d%d%d",&n,&m,&p);
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            insert(i,j,i,j,a[i][j]);
        }
    }
    while(p--){
        int x1,y1,x2,y2,c;
        scanf("%d%d%d%d%d",&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 ++){
            b[i][j] += b[i - 1][j] + b[i][j - 1] -b[i-1][j-1];
        }
    }
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            printf("%d ",b[i][j]);
        }
        printf("\n");
    }
    return 0;
}

总结：

※差分不需要考虑如何去构造函数，因为在最初就假设了数组a与数组b中的元素值全为0，也就符合了b是a的差分，而a是b的前缀和

※所以最终就是要求更新函数,也就是inert()函数！！！