我将 LeetCode 370 题（区间加法）改写为了标准的 NOI/CSP 普及组/提高组风格题目。

本题是差分数组（Difference Array）最基础、最经典的模板题。

[OI 基础训练] 序列操作 (差分数组模板)

一、 题目背景与知识点讲解

在之前的训练中，我们学习了前缀和，它主要用于 “静态数组、频繁查询区间和” 的场景。 如果有这样一个场景：“频繁修改数组的区间（比如给某段区间都加上一个数），最后只查询一次数组的值”，这时候前缀和就无能为力了（因为每次修改都需要 $O(N)$ 重新计算前缀和）。

这时，我们需要引入前缀和的逆运算——差分数组。

1. 什么是差分数组？ 假设有一个原数组 $A$，我们构造一个数组 $D$，使得：

（特别地，定义 $A[0] = 0$，则 $D[1] = A[1] - 0 = A[1]$）

此时，数组 $D$ 就是 $A$ 的差分数组。 反过来，差分数组的前缀和就是原数组：

2. 核心操作：区间修改 如果我们想让原数组 $A$ 在区间 $[L, R]$ 内的每一个数都加上 $V$，我们不需要遍历修改 $A$，只需要修改 $D$ 中的两个点：

1. $D[L] += V$

   • 原理：因为 $A[L]$ 是由 $D[1]...D[L]$ 累加得到的。$D[L]$ 增加了 $V$，那么 $A[L], A[L+1] \dots A[N]$ 都会因此增加 $V$。
   • 效果：这就实现了“从 $L$ 开始往后所有数都加 $V$”。

2. $D[R+1] -= V$

   • 原理：我们只想让 $[L, R]$ 增加，不想让 $R$ 后面的数也增加。
   • 效果：因为 $D[L]$ 的修改导致 $A[R+1]$ 也增加了 $V$，我们在 $D[R+1]$ 处减去 $V$，这就抵消了之前的增加。

3. 复杂度分析

• 暴力修改：每次循环 $L$ 到 $R$，复杂度 $O(N)$。$K$ 次操作总复杂度 $O(K \times N)$。
• 差分修改：每次只改两个点，复杂度 $O(1)$。$K$ 次操作总复杂度 $O(K)$。
• 最后还原：遍历一次求前缀和，复杂度 $O(N)$。
• 总复杂度：$O(N + K)$，效率极高。

二、 题目描述

给定一个长度为 $N$ 的整数序列，初始时序列中每个元素的值都为 $0$。

接下来会有 $K$ 次操作。每次操作会给出三个整数 $L, R, V$，表示将序列中从下标 $L$ 到下标 $R$（包含 $L$ 和 $R$）的所有元素都加上 $V$。

请你输出所有操作完成后，序列中每个元素的值。

注意： 本题采用 1-based 索引（下标从 1 开始）。

输入格式

第一行包含两个整数 $N$ 和 $K$，分别表示序列长度和操作次数。 接下来 $K$ 行，每行包含三个整数 $L, R, V$，表示一次区间修改操作。

输出格式

输出一行，包含 $N$ 个整数，表示操作完成后的序列。每个整数之间用一个空格隔开。

数据范围

• $1 \le N \le 10^5$
• $1 \le K \le 10^5$
• $1 \le L \le R \le N$
• $-1000 \le V \le 1000$
• 结果保证在 32 位有符号整数范围内（但在竞赛中建议使用 long long 以防万一）。

样例输入

5 3
1 3 2
2 4 3
3 5 -2

样例输出

2 5 3 1 -2

样例解释

1. 初始状态：[0, 0, 0, 0, 0]
2. 操作 1 3 2 (1~3 加 2)：[2, 2, 2, 0, 0]
3. 操作 2 4 3 (2~4 加 3)：[2, 5, 5, 3, 0]
4. 操作 3 5 -2 (3~5 减 2)：[2, 5, 3, 1, -2]

三、 标准代码 (C++14 OI风格)

/**
 * 题目：序列操作 (区间加法)
 * 知识点：差分数组 (Difference Array)
 * 时间复杂度：修改 O(K), 还原 O(N), 总计 O(N+K)
 * 空间复杂度：O(N)
 */

#include <iostream>
#include <vector>

using namespace std;

// 使用 long long 防止多次累加后溢出，虽然本题数据范围 int 也可以
typedef long long ll;

const int MAXN = 100005;
// 定义差分数组
// 注意：数组大小要开到 N+2，因为差分操作会访问 diff[R+1]，防止越界
ll diff[MAXN]; 

int main() {
    // 1. IO 优化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    // 2. 处理 K 次区间修改操作
    for (int i = 0; i < k; ++i) {
        int l, r, v;
        cin >> l >> r >> v;

        // 核心差分操作：
        // 起点 +v
        diff[l] += v;
        // 终点的下一位 -v
        diff[r + 1] -= v; 
    }

    // 3. 还原数组 (求前缀和)
    // 此时 diff[i] 已经变成了原数组的第 i 项的值
    // 我们可以直接在 diff 数组上进行累加，节省空间
    // 也可以用一个变量 current_val 来累加并输出
    
    ll current_val = 0;
    for (int i = 1; i <= n; ++i) {
        current_val += diff[i];
        cout << current_val << (i == n ? "" : " ");
    }
    cout << endl;

    return 0;
}

四、 教学备课重点 (教练参考)

1. 数组越界陷阱：

   • 这是差分数组最容易犯错的地方。操作公式是 diff[r + 1] -= val。如果 $R = N$，那么 diff[N + 1] 就会被访问。
   • 解决方案：声明数组大小时，至少要设为 $N + 2$。或者在代码中加 if (r + 1 <= n) 的判断（但在 OI 中，开大数组通常更方便）。

2. 初始非零的情况：

   • 本题假设初始全是 0，所以不需要先构造差分数组。
   • 进阶提问：如果输入第二行给出了初始数组 $A$ 怎么办？
   • 回答：
     • 方法一：先根据 $A$ 计算出初始的 diff（diff[i] = A[i] - A[i-1]），然后再做区间修改。
     • 方法二（偷懒法）：把初始数组 $A$ 看作是 $N$ 次区间修改操作（第 $i$ 次是在区间 $[i, i]$ 上加上 $A[i]$）。

3. 与线段树的区别：

   • 差分数组只能处理**“先进行所有修改，最后进行一次查询”**的情况（离线问题）。
   • 如果题目是“边修改，边查询”，或者“区间求最大值”，差分数组就不够用了，那时需要引入线段树 (Segment Tree) 或 树状数组 (Binary Indexed Tree)。但在普及组/CSP-J 阶段，差分数组是必考基础。

4. 实际应用：

   • 差分思想不仅用于数组，还可以用于时间轴问题。例如：公交车时刻表，每个人在 $start$ 上车，在 $end$ 下车，求车上人数最多的时候。这就是典型的区间加法问题。