题目描述

给定一个长度为n的整数序列，对每一个输入{l,r,c}，修改在位置范围[l,r]的元素，使每个元素都加上数值c；执行多次这种输入后，输出修改后的整数序列；

样例

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

算法1

差分 $O(n)$

差分是前缀和的逆运算，可以构造一个新的序列b[n]，它的每一个元素b[i]=a[i]-a[i-1]，则a[n]为b[n]的前缀和；由在某一个范围[l,r]中，都有加上数值c的需求，则如果对这样的要求使用暴力加法的话，将会对每一次这种需求都有O(n)的时间需求，但使用差分序列的话，则只需要进行b[l]+=c，b[r+1]-=c这两步操作即可使其前缀和序列a[n]完成相同操作，而仅需O(1)的时间复杂度；

时间复杂度 O(n)

参考文献

C++ 代码

#include<iostream>
using namespace std;

const int N = 100010;
int a[N], b[N];

int main()
{
    int n, q;
    cin>>n>>q;
    for(int i = 1; i <= n; ++i){
        scanf("%d", &a[i]);
        b[i] = a[i] - a[i-1];
    }//输入时顺便建立差分序列数组；
    while(q--){
        int l, r, c;
        scanf("%d %d %d", &l, &r, &c);
        b[l] += c;        //使a的起点元素加上c，则以后的每个前缀和元素都会加上这个c
        b[r+1] -= c;      //记得在a不再加元素c的位置将其减去
    }
    for(int i = 1; i <= n; ++i){
        a[i] = a[i-1] + b[i];    //将差分序列还原；
        cout<<a[i]<<' ';
    }
    return 0;
}