🌹作者:云小逸
📝个人主页: 云小逸的主页
📝Github: 云小逸的Github
🤟motto:要敢于一个人默默的面对自己， ==强大自己才是核心==。不要等到什么都没有了，才下定决心去做。种一颗树，最好的时间是十年前，其次就是现在！学会自己和解，与过去和解，努力爱自己。==希望春天来之前，我们一起面朝大海，春暖花开！==🤟
👏专栏：C++👏 👏专栏：Java语言👏
👏专栏：C语言初阶👏👏专栏：数据结构👏

前言

今天这篇文章是接着上一篇文章【差分】展开说差分在题目中的妙用。如有错误，请私信告知，望见谅！
——————————————————————————————

首先先写上几句话：献给坚持创作的我和点开这篇文章希望进步的你

​

改变数组元素【一维差分】

题目：

给定一个空数组 V 和一个整数数组 a1,a2,…,an。现在要对数组 V 进行 n 次操作。
第 i 次操作的具体流程如下：

从数组 V 尾部插入整数 0。
将位于数组 V 末尾的 ai 个元素都变为 1（已经是 1 的不予理会）。

注意：
ai 可能为 0，即不做任何改变。
ai 可能大于目前数组 V 所包含的元素个数，此时视为将数组内所有元素变为 1。
请你输出所有操作完成后的数组 V。

输入格式

第一行包含整数 T，表示共有 T 组测试数据。每组数据第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

每组数据输出一行结果，表示所有操作完成后的数组 V，数组内元素之间用空格隔开。

数据范围

1≤T≤20000,
1≤n≤2×105,
0≤ai≤n,
保证一个测试点内所有 n 的和不超过 2×105。

输入样例：

3
6
0 3 0 0 1 3
10
0 0 0 1 0 5 0 0 0 2
3
0 0 0

输出样例：

1 1 0 1 1 1
0 1 1 1 1 1 0 0 1 1
0 0 0

题目分析：

可能你读完题，一下子没有理解是什么意思，没事，接下来这张动图便于你的理解：

希望看完这个动图你能理解这个题目

其实我们可以从题目这句话入手进行解题：
在这个数组内看这个数是0还是1：可以看这个数被操作的次数，如果操作0次，则是0，操作不是0次，则是1.

代码：

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N=200010;

int n;
int b[N];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        memset(b,0,(n+1)*4);
        for(int i=1;i<=n;i++)
        {
            int a;
            scanf("%d",&a);
            int l=max(1,i-a+1),r=i;
            
            b[l]++;
            b[r+1]--;
        
        }
        for(int i=1;i<=n;i++)
        {
            b[i]+=b[i-1];
            cout<<!!b[i]<<" ";
        }
        puts(" ");
    }
    
    return 0;
}

代码讲解：

1.memset函数

上面是memset函数的官方解释。
这里使用memset要注意,因为这里的测试数据比较大，如果直接初始化，代码可能过不了，因此要么使用for循环要么使用memset只初始化前n+1的数据也是可以的。

2.边界的代换

3.一维差分的模版：

差分矩阵【二维差分】

题目：

输入一个 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

题目分析：

这道题目的意思是：给定原矩阵a[][],构造差分矩阵b[][]，使得a[][]是b[][]的二维前缀和。
即ai是b1到bi的矩阵，就是下图的意思。

核心思想：【二维差分】

以（x1,x2）为左上角，（x2,y2）为右上角的子矩阵中的所有数ai，加上C（常数）
如：

 b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;

代码：

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], b[N][N];

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, &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];

    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ ) printf("%d ", b[i][j]);
        puts("");
    }

    return 0;
}

​

最后

十分感谢你可以耐着性子把它读完和我可以坚持写到这里，送几句话，对你，也对我：

​

最后如果觉得我写的还不错，请不要忘记==点赞==✌，==收藏==✌，加==关注==✌哦(｡･ω･｡)

愿我们一起加油，奔向更美好的未来，愿我们从懵懵懂懂的一枚==菜鸟==逐渐成为==大佬==。加油，为自己点赞！
​

​