题解 | #【模板】差分#

这是一个典型的差分数组（Difference Array）应用场景。核心思想是：

• 问题特点：只进行区间修改，且无需在中间过程查询，最终一次性输出结果。这允许我们将"区间操作"转化为"点操作"。
• 关键观察：如果对原数组的区间 [l, r] 增加 d，等价于在差分数组上 diff[l] += d 且 diff[r+1] -= d。
• 最终还原：差分数组的前缀和即为原数组的修改结果。

该思路避免了每次操作都遍历区间内的所有元素，将单次修改复杂度从 O(长度) 降至 O(1)。

算法步骤

1. 初始化差分数组
   读取初始数组 a[1..n]，构造差分数组 diff[1..n]：

   • diff[1] = a[1]
   • 对于 i = 2..n：diff[i] = a[i] - a[i-1]

2. 处理所有修改操作
   对每次操作 (l, r, d)：

   • 执行 diff[l] += d
   • 若 r+1 ≤ n，执行 diff[r+1] -= d（处理边界）

3. 还原最终数组
   计算前缀和得到最终结果 result[1..n]：

   • result[1] = diff[1]
   • 对于 i = 2..n：result[i] = result[i-1] + diff[i]

4. 输出结果
   按顺序输出 result[1..n] 的 n 个整数。

计算复杂度

代码实现

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    vector<ll> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    vector<ll> diff(n + 1, 0);

    for (int i = 0; i < n; i++) {
        diff[i] = a[i] - (i > 0 ? a[i - 1] : 0);
    }

    while (q--) {
        int l, r;
        ll d;
        if (!(cin >> l >> r >> d)) break;

        int l_idx = l - 1;
        int r_idx = r - 1;

        diff[l_idx] += d;

        if (r_idx + 1 < n + 1) {
            diff[r_idx + 1] -= d;
        }
    }

    vector<ll> b(n);
    ll curSum = 0;

    for (int i = 0; i < n; i++) {
        curSum += diff[i];
        b[i] = curSum;
    }

    for (int i = 0; i < n; i++) {
        cout << b[i] << (i == n - 1 ? "\n" : " ");
    }

    return 0;
}