#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<long long> a(n + 2); // a[1..n]
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    // !!构建差分数组 d[1..n+1]
    vector<long long> d(n + 2, 0);
    for (int i = 1; i <= n; ++i) {
        d[i] = a[i] - a[i - 1];
    }




    // m 次操作，每次修改区间 [l, r] 加上 k
    for (int i = 0; i < m; ++i) {
        int l, r;
        long long k;
        cin >> l >> r >> k;
        d[l] += k;
        d[r + 1] -= k;
    }

    // 还原最终数组：前缀和
    for (int i = 1; i <= n; ++i) {
        a[i] = a[i - 1] + d[i];
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}

朴素写法是：

for (int i = l; i <= r; ++i) {
    a[i] += k;
}

⛔ 坏处：每次操作都是 O(r−l+1)，多次就会超时。

✅ 差分数组思想：用一种技巧，让区间修改变成“常数时间”

我们定义一个新的数组 d[i]，表示：

d[i] = a[i] - a[i-1]

也就是说，d 数组是 a 数组的“变化量”。

举个例子：

a = [1, 2, 3, 4, 5]
=> d = [1, 1, 1, 1, 1] （因为 a[i]-a[i-1] 都是1）

现在我们想把区间 [2,4] 加上 10，该怎么办呢？

只需要改两项：

d[2] += 10;
d[5] -= 10;  // 4的下一位是5

🤔 为什么这样就可以？

假设你后面用前缀和恢复回 a：

a[1] = d[1]
a[2] = d[1] + d[2]
a[3] = d[1] + d[2] + d[3]
...

所以这个差分数组在恢复的时候会自动把 [2, 3, 4] 都加上 10。

来看完整过程：

原数组：       [1, 2, 3, 4, 5]
原差分 d：     [1, 1, 1, 1, 1]
修改 d：       d[2] += 10, d[5] -= 10
更新后 d：     [1, 11, 1, 1, -9]

前缀还原 a：
a[1] = 1
a[2] = 1 + 11 = 12
a[3] = 1 + 11 + 1 = 13
a[4] = 1 + 11 + 1 + 1 = 14
a[5] = 1 + 11 + 1 + 1 - 9 = 5

结果：       [1, 12, 13, 14, 5] ✅