12722. 差分入门 题解
难度：⭐⭐⭐⭐
知识点：差分
题目链接
序言：
第一次写在添柴上的题的题解，嗯嗯呃呃....
1. 入手程序
这道题可以约等于一个裸题，就是一个基本的区间修改题目，连查询都不需要！
但这道题的数据不小，不能直接一个数组直接进行该动，可以作为差分的入门题~
2. 编程思路
神马是差分呢？差分指的是每一次改动不直接影响结果，而是把改动存储在一个临时空间中。
比如这一题，不把每次的改动直接放在答案数组a里，而是放在差分数组k里
（然后这样再那样在布拉布拉。。。。）
好吧，我承认老师讲的这一段真的很难懂
那我来用样例说明一下
开始时a数组为：1 5 7 3 6 9
实际变化过程为：
1 5 7 3 6 9
1 5 7 6 9 12
1 6 8 7 10 12
1 6 10 9 12 14
k[i]初始化为a[1],k [i]初始化为a[i]-a[i-1]
f[i]=a[i]-a[i-1];
结果为：1，4，2，-4，3，3
第一个步骤：第四到第六位加3
k对应操作：第四位+3，第七位-3（当然，本样例没有第七位）
第二个步骤：第二到第五位加1
k对应操作：第二位+1，第六位-3
第三个步骤：第三到第六位加2
k对应操作：第三位+2，第七位-2（同上）
代码就是：
f[A]+=C;
if(B!=n)
{
f[B+1]-=C;
}
最后不要忘了k数组要逐位加到a数组上哦~
3. AC代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int A,B,C;
int a[100005],f[100005];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
f[i]=a[i]-a[i-1];
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>A>>B>>C;
if(A>B)
{
swap(A,B);
}
f[A]+=C;
if(B!=n)
{
f[B+1]-=C;
}
}
for(int i=1;i<=n;i++)
{
a[i]=a[i-1]+f[i];
cout<<a[i]<<" ";
}
return 0;
}
