蓝桥杯备考：差分算法模板题(差分算法详解）
【模板】差分
代码
#include <iostream>
using namespace std;
const int N = 1e5+10;
typedef long long LL;
LL a[N],f[N];
int n,m;
int main()
{
cin >> n >> m;
for(int i = 1;i<=n;i++)
{
cin >> a[i];
f[i]+=a[i];
f[i+1]-=a[i];
}
while(m--)
{
int l,r,k;cin >> l >> r >> k;
f[l]+=k;f[r+1]-=k;
}
for(int i = 1;i<=n;i++)
{
a[i] = a[i-1]+f[i];
}
for(int i = 1;i<=n;i++) cout << a[i] << " ";
}这道题的暴力解法就是用双层for循环遍历l到r来修改，时间复杂度就是O（m*n），经计算是10的十次方，是会超时的
我们选择用差分算法来进行优化，那么什么是差分数组呢，就是说经过预处理后每个元素都等于该元素减去上一个元素的差值，就叫做差分数组
差分数组的作用就是对某一区间同时加减一个数，我们来画一个图
可见，差分数组的公式是f[i] = a[i]-a[i-1]
2.利用差分数组修改区间
我们要让[L,R]区间+k，只需要让f[l]+k,f[r+1]-k就行了
3.如何还原出修改后的原数组呢？我们只要对差分数组进行一次前缀和就行了
f1 = a1 ----- a1 = f1
f2 = a2-a1 ----- a2 = f2+a1=f2+f1
f3 = a3-a2 ------ a3 = f3+a2 = f1+f2+f3
......................................
f[i] = ai - ai-1 ------------ ai = f[i]+ai-1 = f1+f2.....+fi