差分

差分和前缀和是密不可分的，如有一个数组a，就会对应有一个差分数组b。差分数组b的特性是：

a[i]=b1+b2+b3+…+bi,即为将数组a看做b的前缀和数组,a与b互为逆运算.

一维差分

简单分析

一维差分就是由一维数组组成的差分，主要运用差分数组的特性将求原数组a(b的前缀和数组)的某子区间进行加减操作从O(n)转化为O(1).

如：输入一个长度为 n 的整数序列。接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r]之间的每个数加上 c。请你输出进行完所有操作后的序列。

代码

#include<iostream>
#include<stdio.h>
using namespace std;
#define N 100010
int a[N],b[N];
void insert(int l,int r,int num){
    b[l] += num; //将第l个加上num因为a为b的前缀和所以l之后所有a[i]都会加上num
    b[r+1] -= num; //由于只需要加到r所以需要将r+1处的b减去num用来抵消上面加的num
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++) {
        scanf("%d",&a[i]); //录入原数组
        insert(i,i,a[i]); //求差分数组 就等于初始化原数组为0将每一位都加上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) {
        a[i] = a[i-1] + b[i];  //重新逆运算求回原数组(即为求b数组的前缀和)
        printf("%d ",a[i]);
    }

    return 0;
}

二维差分

简单分析

二维差分与一维类似只不过由线段变为矩阵，差分数组b变为一个矩阵，作用依然是运用差分数组的特性将求原数组a(b的前缀和数组)的某子区间进行加减操作从O(n)转化为O(1).

如：输入一个 n 行 m 列的整数矩阵，再输入 q个操作，每个操作包含五个整数 x1,y1,x2,y2,c其中 (x1,y1)(x1,y1) 和 (x2,y2)(x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。每个操作都要将选中的子矩阵中的每个元素的值加上 c。请你将进行完所有操作后的矩阵输出。

代码

差分公式分析

#include <iostream>
#include <stdio.h>
using namespace std;
#define N 1010
int a[N][N],b[N][N];

void insert(int x1,int y1,int x2,int y2,int c){
    b[x1][y1] += c; //先将起始坐标的差分数组+c等同于对于a数组(b的前缀和数组)x1,y1之后的整个矩阵都加上了c
    //由于只需要加到x2，y2坐标 就需要把x2，y2之后多余的矩阵减去c与刚才加的c抵消
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c; //但是会减去两次一个重复的矩阵需要加回来一个
}


int main(){
    int n,m,q;
    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]); //录入原矩阵
            //同样假设一开始a数组都为0则差分数组b也都为0，这样求a数组的差分数组就等同于从一开始的0插入a[i][j]依次得到新的差分数组
            //当原数组录入完则差分数组也计算完
            insert(i,j,i,j,a[i][j]);
        }
    }
    while(q--){ //q次询问
        int x1,y1,x2,y2,c;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c); //录入两坐标和,需加的值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 - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j]; //二维前缀和公式
            printf("%d ",a[i][j]); //边求边打印
        }
        printf("\n");
    }
    return 0;
}