1、差分算法用于优化:频繁加减任意区间值
2、算法思想
(1)首先将原数组a转换为差分数组b。转换公式为:b[i] = a[i] -a[i-1];
(2)对原数组a中下标l到r之间所有元素加上c,转换为,对差分数组b中下标l的元素加上c,对下标r+1的元素减去c,即:b[l] + c; b[r+1] – c;
(3)对差分数组b,进行前缀和操作,得到修改后的原数组a,即:a[i] = a[i-1] +b[i];
3、算法模板
int a[100010], b[100010];
int main()
{
int n, m;
cin>>n>>m;
for (int i = 1; i <= n; i++)
{
cin>>a[i];
b[i] = a[i] - a[i - 1]; //构建差分数组
}
int l, r, c;
for(int i=1;i<=m;i++)
{
cin>>l>>r>>c;
b[l] += c; //将序列中[l, r]之间的每个数都加上c
b[r + 1] -= c;
}
for (int i = 1; i <= n; i++)
{
a[i] = b[i] + a[i - 1]; //前缀和运算
cout<<a[i]<<" ";
}
return 0;
}