题解 | #【模板】差分#

因为本题直接解决实现起来不难，故一开始选择直接暴力解法。
每次接受l，r，k后，直接遍历数组中的第l个到第r个元素，将其加k。

这种做法时间复杂度O(n^2)，空间复杂度O(1)。会在第七个用例(共8个)处超时。由于用例输入数据量过大，无法验证是由于循环逻辑出错导致超时，还是由于算法时间复杂度过高导致超时。这里暂且认为是由于时间复杂度过高导致超时。转而寻找时间复杂度更低的做法。

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    vector<long long> arr(n, 0);
    for(int i = 0;i < n;i++){
        cin >> arr.at(i);
    }
    for(int i = 0;i < m;i++){
        int l, r, k;
        cin >> l >> r >> k;
        l--;
        r--;
        for(int j = l;j < r + 1;j++){
            arr.at(j) += k;
        }
    }
    for(int i = 0;i < n;i++){
        cout << arr.at(i) << ' ';
    }
    return 0;
}

考虑一种方法，不用每次都遍历数组，对l到r之间的数进行修改，而是记录每次的修改，最后直接得到最终修改后的数组。
为了实现这一目标，我们要先建立一个数组sum。在m次循环中，每一次接收到l,r,k时，使sum.at(l-1)+=k，使sum.at(r)-=k。这么做是为下一步求出每一位的最终改变量做准备。
在经过m次循环后，sum中已经存储了每一位改变的值的信息，但并不能直接通过sum.at(i)得到arr.at(i)。所以还需要对sum求一次前缀和。
经过求前缀和的sum中，sum.at(i)所对应的就是arr.at(i)需要改变的值。用arr.at(i)+sum.at(i)即可得到最终结果。

这种做法不用在m次循环中每次都遍历原始数组arr，而是直接将改变的信息记录在sum中，这一步时间复杂度仅为O(1)。所以整体时间复杂度为O(n)。由于借用了sum数组作为辅助数组，空间复杂度为O(n)。
这种做法可以看作是通过空间换时间对上面那种做法的改进。

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    vector<long long> arr(n, 0);
    vector<long long> sum(n, 0);
    for(int i = 0;i < n;i++){
        cin >> arr.at(i);
    }
    for(int i = 0;i < m;i++){
        int l, r, k;
        cin >> l >> r >> k;
        sum.at(l - 1) += k;
        if(r < n){
            sum.at(r) -= k;
        }
    }
    for(int i = 1;i < n;i++){
        sum.at(i) += sum.at(i - 1);
    }
    for(int i = 0;i < n;i++){
        arr.at(i) += sum.at(i);
        cout << arr.at(i) << ' ';
    }
    return 0;
}