差分数组

• 一维差分
• • 差分数组的作用
• 差分矩阵
• 结语

一维差分

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

输入格式
第一行包含两个整数 n 和 m

第二行包含 n 个整数，表示整数序列。

接下来 m行，每行包含三个整数 l，r，c，表示一个操作。

输出格式
共一行，包含 n 个整数，表示最终序列。

数据范围

1≤n,m≤100000
,
1≤l≤r≤n
,
−1000≤c≤1000
,
−1000≤整数序列中元素的值≤1000

输入样例：

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例：

3 4 5 3 4 2

本题大概题意是求出一个数组的差分数组，假定原数组为a[],
所求差分数组 b[],公式为 b[i]=a[i]-a[i-1] ,可知：

差分数组b[]的前缀和数组，就是原数组a[],也就是说，
差分 和 前缀和互为逆运算

差分数组的作用

差分数组能快速的对给定范围内的数组统一的增加或者减少大小，
要让原数组a[]在[i,j]的范围内的数值都加上一个value，那么只需要在差分数组b[]上进行改动：

b[i]+=c 
b[j+1]-=c

根据原数组是差分数组的前缀和这一原理很好理解

解题思路：

我们可以假定原数组元素全为0，
那么差分数组也全为0，
那么我们可以遍历一遍差分数组，然后对其进行插入操作

for(int i=1;i<=n;i++) insert(i,i,a[i]);//insert函数里面改变的是b数组的值

1.现在所求的b[]数组便是一个差分数组，
当然也可以用**b[i]=a[i]-a[i-1]**来求差分数组

2.然后就是在差分数组内进行插入修改
3.最后对整个差分数组进行一次前缀和
4.输出数组即可

代码：

#include<iostream>

using namespace std;

const int N=100010;

int a[N];
int b[N];

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

int main()
{
    int n,m;
    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 ",b[i]);
    
    return 0;

}

差分矩阵

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

输入格式
第一行包含整数 n,m,q

接下来 n 行，每行包含 m个整数，表示整数矩阵。

接下来 q 行，每行包含 5个整数 x1,y1,x2,y2,c，表示一个操作。

输出格式
共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。

数据范围

1≤n,m≤1000
,
1≤q≤100000
,
1≤x1≤x2≤n
,
1≤y1≤y2≤m
,
−1000≤c≤1000
,

−1000≤矩阵内元素的值≤1000
输入样例：

3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1

输出样例：

2 3 4 1
4 3 4 1
2 2 2 2

本题就是求一个二维差分矩阵，大致思路和上题一致，在求差分时需要画图理解一下

红颜色部分是我们需要改变数组的区域

先根据公式 b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+b[i][j];

在画图可知

就可以理解公式了，
题解：
先求出差分数组
在根据题目要求对差分数组进行插入操作
然后求出差分数组的前缀和数组
最后数组该数组即可

代码：

#include<iostream>

using namespace std;
const int N=1010;

int a[N][N];
int b[N][N];

void insert(int x1,int y1,int x2,int y2,int val)
{
    b[x1][y1]+=val;
    b[x1][y2+1]-=val;
    b[x2+1][y1]-=val;
    b[x2+1][y2+1]+=val;
}


int main()
{
    int n,m,q;
    cin>>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++)
        {
            insert(i,j,i,j,a[i][j]);
        }
    }
    
     while(q--)
     {
         int x1,y1,x2,y2,c;
         cin>>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]+b[i][j];
        }
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
           cout<<b[i][j]<<' ';
        }
        cout<<endl;
    }
    
    return 0;
}

结语

如果觉得有帮助的话，记得
一键三连哦ヾ(≧▽≦*)o。