【差分数组】

一维差分

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

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

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

接下来 m行每行包含三个整数 lrc表示一个操作。

输出格式
共一行包含 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。