题目

https://www.acwing.com/problem/content/799/

算法思想

差分是前缀和的逆运算，对于 a₁, a₂, ..., a_n，构造 b₁, b₂, ..., b_n，使得 a_i = b₁ + b₂ + ... + b_i 。

b₁ = a₁

b₂ = a₂ - a₁

b₃ = a₃ - a₂

b_n = a_n - a_n-1

即 b 数组称为 a 数组的差分，a 称为 b 数组的前缀和。如果有 b 数组，可以用 O(n) 的时间得到 a。

通过差分可以用 O(1) 的时间复杂度达到对 a 数组在 [l, r] 区间内的每个数字 +c，即 b_l + c，b_r+1 - c。

如何将 a 转为 b？

假定 a 数组初始全为 0，对应差分数组 b 也全为 0，对 a_i 赋值操作，可以看成是在 [i, i] 区间内 + a_i ，即 b_i + a_i，b_i+1 - a_i。

题解

#include <iostream>
using namespace std;

const int N = 100010;

int arr[N];

void insert(int i, int j, int num)
{
    arr[i] += num;
    arr[j+1] -= num;
}

int main()
{
    int n, m, tmp;
    std::cin >> n >> m;
    
    for(int i = 1; i <= n; ++i)
    {
        std::cin >> tmp;
        insert(i, i, tmp);
    }
    
    int l, r, c;
    
    while(m--)
    {
        std::cin >> l >> r >> c;
        insert(l, r, c);
    }
    
    for(int i = 1; i <= n; ++i)
    {
        arr[i] += arr[i-1];
        std::cout << arr[i] << " ";
    }
    
    return 0;
}

复杂度

时间复杂度：O(n)，空间复杂度：O(1)