企业官网建设流程全解析

做在线题库刷题时，几乎每个人都会遇到 P2367 这道题。题目名字叫《语文成绩》，第一次看到真以为要和语文单词打交道，点进去才发现是给一排成绩做区间加减，最后找最小值。这题考察的核心就是差分算法。差分思想不算复杂，但很多初学者容易卡在“为什么区间加一次，只要改两个位置”，甚至有人看完整套模板还是不敢用。这篇文章就从题目到代码，把差分算法的来龙去脉讲清楚。如果你刚学完前缀和、想搞明白差分的实际用法，或者刷题频繁遇到超时想找优化思路，都可以直接照着这篇文章的思路走一遍。

1. 先读懂题目：P2367 到底在算什么

1.1 原题模型与输入输出

P2367 的题目背景很简单：假设班里有 n 个学生，老师手里有他们某次语文考试的成绩。接着会进行 m 次调整，每次调整会把第 l 个到第 r 个学生的成绩都加上同一个分数 c。所有调整结束之后，老师想知道全班的最低分是多少。

要注意的是，这个“加上同一个分数”是在现有成绩上直接累加，不是覆盖成某个固定成绩。也就是说，如果一个学生的成绩原本是 80，区间调整让 [5,10] 加 3，那么他的成绩变成 83，而不是被改成 3。这一点很关键，很多人做的时候把加法理解成赋值，结果整个差分思路全部变形。

输入格式通常分成三部分：先给两个整数 n 和 m，代表学生人数和调整次数。然后给出 n 个学生的初始成绩。接下来 m 行，每行三个整数 l、r、c，表示对第 l 到第 r 个学生加上 c 分。输出只需要一个整数，就是最终所有学生成绩的最小值。

这种题看起来像模拟题，但数据规模不会让你真的去“模拟”。n 和 m 稍微大一点，比如到十万、百万级别，暴力做法就会彻底卡死。这也是为什么差分算法在这道题里几乎是标准答案。

1.2 暴力修改的瓶颈在哪里

最容易想到的做法是：用数组存每个学生的成绩，每读到一次调整，就用一个 for 循环从 l 跑到 r，每次执行a[i] += c。所有调整结束之后，再扫一遍数组找最小值。

这个思路本身没错，但时间复杂度是 O(nm)。假设 n 和 m 都是 10^5，循环次数就是 10^10，普通评测环境下基本不可能通过。更极端一点，如果 n 和 m 都到 10^6，那就不用跑了，直接放弃。

有人可能会想，能不能用线段树或者树状数组？当然可以，但杀鸡用牛刀。P2367 只要求最终结果，而且所有操作都是“区间加”，没有中途查询、没有删改、没有在线询问，这种情况下差分算法是最简洁高效的方案。

1.3 关键突破口：只关心最终结果

这道题之所以能用差分，是因为我们不需要知道每一次调整之后班级的最低分，只需要最后一次调整结束后的最小值。差分算法的核心思路是：不直接维护每个学生的真实成绩，而是维护“相邻两个学生成绩之间的差值”。

如果把真实成绩看成一座起伏的山，那么差分数组记录的就是每个“坡段”的变化量。对一段连续区间做加法时，整段内部的相对高低关系不会变，真正变化的只有区间的起点和终点外侧。于是我们只需要在起点做个标记、在终点外做个抵消，就能把整段区间的修改记录下来。最后再顺着从第一个学生到最后一个学生，把差分累加回去，就能还原出每个人的最终成绩。

这个思路说起来很像记账：不用逐笔更新所有账户余额，只需要在开始发钱的节点记一笔增加，在停止发钱的节点记一笔减少，最后汇总时每过一个节点就累加上变化量。理解了这层逻辑，后面所有代码都非常自然。

2. 差分数组原理：区间加法变成两次单点修改

2.1 差分数组的定义与构造

先定义一下符号。设原始成绩数组为a[1]到a[n]，差分数组为d[1]到d[n]，差分数组满足：

• d[1] = a[1]
• d[i] = a[i] - a[i-1]，其中 i 从 2 开始。

也就是说，差分数组里存放的是“相邻两个原始元素之间的差值”。第 i 个原始值越大，对应位置的 d[i] 通常是正数；第 i 个值相比前一个变小，d[i] 就是负数。

举个例子，如果成绩数组是：

a = [3, 5, 7, 2, 8]

那么差分数组就是：

d[1] = 3 d[2] = 5 - 3 = 2 d[3] = 7 - 5 = 2 d[4] = 2 - 7 = -5 d[5] = 8 - 2 = 6

构造差分数组很简单，无非是在读入数组时，边读边算。实际操作中，甚至不需要把原始数组完整保留一份：每读到一个a[i]，就把它和a[i-1]的差值写进d[i]即可。不过初次学习时，先把原始数组存下来再构造，思路更清楚，不容易出错。

2.2 从差分还原原数组：前缀和

有了差分数组，如何还原出真实成绩？答案就是做一遍前缀和。因为：

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

所以只要从前往后累加差分数组，就能得到每一个位置的原始值。这里的累加过程，就是我们常说的前缀和思想。差分和前缀和是逆运算关系：差分可以帮助你把区间修改变成单点修改，前缀和可以帮助你把区间查询变成差分数组上的快速计算。

在实际代码里，我们甚至不需要单独开一个数组来存还原后的成绩。只要用一个变量cur保存当前累加结果，cur += d[i]得到的就是第 i 个学生的最终成绩，顺手比较一下就能找出最小值。

2.3 区间加法的核心推导

现在重点来了：如果要把a[l]到a[r]全部加上 c，差分数组会发生什么变化？

考虑任意相邻位置 i-1 和 i，如果 i 和 i-1 都在区间内部，那么两个数都加了同一个 c，它们之间的差值不会变，所以d[i]不用动。只有区间的两个边界会影响差分数组：

• 在l位置，a[l]加 c，但a[l-1]没有加 c，所以d[l]会增加 c。
• 在r+1位置，a[r+1]没有加 c，但a[r]加了 c，所以d[r+1]会减少 c。

因此区间加操作可以用两次单点修改代替：

d[l] += c; d[r + 1] -= c;

这就是整个差分算法最核心的公式。如果你把差分数组的变化量做过一遍前缀和，就会发现从 l 开始，累加量多出 c，一直持续到 r；到 r+1 的时候，因为前面减掉 c，累加量又恢复了原来的状态。这样正好只影响[l, r]这一整段。

2.4 一个手算示例

光背公式没用，最好亲手推一遍。假设初始成绩仍然为：

[3, 5, 7, 2, 8]

现在要对第 2 到第 4 个学生加上 5，也就是区间[2,4]，预期结果是：

[3, 10, 12, 7, 8]

对应差分数组原本是：

[3, 2, 2, -5, 6]

执行两次单点修改：

• d[2] += 5，变成2 + 5 = 7
• d[5] -= 5，因为 r+1 = 5，所以6 - 5 = 1

修改后的差分数组是：

[3, 7, 2, -5, 1]

然后从头累加：

• cur = 3，得到第 1 个成绩 3
• cur = 3 + 7 = 10，得到第 2 个成绩 10
• cur = 10 + 2 = 12，得到第 3 个成绩 12
• cur = 12 - 5 = 7，得到第 4 个成绩 7
• cur = 7 + 1 = 8，得到第 5 个成绩 8

和预期完全一致。注意看，差分数组只在两个位置发生了变动，中间那些 d[i] 全部原封不动。这就是“区间加 O(1)”的真相。

3. 完整解题流程：从差分构造到输出答案

3.1 第一步：读入成绩并初始化差分数组

面对这种题，我的习惯是先确定数组范围。如果 n 最大到 10^6，那么数组至少要开n + 2，因为后续操作会访问d[r+1]，而 r 最大等于 n，所以r+1最大是n+1。为了保险，干脆多开两个位置。

构造差分数组时，如果原始成绩已经全部读入，可以这样写：

vector<long long> d(n + 2, 0); for (int i = 1; i <= n; i++) { cin >> a[i]; } d[1] = a[1]; for (int i = 2; i <= n; i++) { d[i] = a[i] - a[i - 1]; }

如果你不想额外存a，也可以一边读入一边构造：

int pre = 0; for (int i = 1; i <= n; i++) { long long x; cin >> x; d[i] += x; // 等价于让差分数组记录当前位置的值 d[i + 1] -= x; // 让后续位置的前缀和不再包含 x pre = x; }

第二种写法更省空间，但是第一次接触时容易把自己绕晕。我个人建议新手先用第一种写法，保证逻辑清晰，代码写对了再追求节省数组。

3.2 第二步：处理 m 次区间加法

差分数组构造好之后，剩下的操作就简单了。每次读入l, r, c，直接执行：

d[l] += c; d[r + 1] -= c;

这里不需要循环，不需要判断区间长度，也不需要担心区间会不会重叠。即使多次操作都落在同一个位置，也只是把这个位置的偏移量累加。例如区间[1,3]加 2、区间[2,5]加 3，那么d[2]会被加两次吗？不会，第一次区间会修改 d[1] 和 d[4]，第二次会修改 d[2] 和 d[6]，它们互不干扰，各自累加到对应的位置上。

初学者最容易问的问题：如果 l 和 r 输入时从 0 开始编号怎么办？P2367 这类题通常默认从 1 开始编号，成绩数组的下标也从 1 开始。如果你遇到从 0 开始编号的题目，只需要把 l 和 r 都加 1 再使用差分公式。实际操作时，最好先在代码里把下标转换好，不要在差分公式里反复加加减减，容易把自己搞混。

3.3 第三步：前缀和还原并统计最小值

所有 m 次操作处理完之后，差分数组 d 里记录的是累积变化量。接下来从 1 到 n 扫一遍，用一个变量cur累加 d[i]，得到的值就是第 i 个学生的最终成绩。

统计最小值时，可以先把答案初始化为一个极大值，比如LLONG_MAX或者1e18。然后每得到一位学生成绩，就和当前答案比较：

long long cur = 0; long long ans = LLONG_MAX; for (int i = 1; i <= n; i++) { cur += d[i]; ans = min(ans, cur); } cout << ans << '\n';

这里要特别注意：最终答案是“还原后成绩的最小值”，不是差分数组的最小值。差分数组记录的是差值，差值最小不代表真实成绩最小。比如差分数组里可能有一堆负数，但如果原始成绩整体很高，这些负数累计之后依然很大，仍然不可能是全班最低分。所以一定要先完成前缀和还原，再比较大小。

3.4 为什么这样设计的正确性

如果要把这个思路讲给初学者，我通常会从“变化量”的角度解释。一次区间加法，本质上是对区间内所有元素施加一个统一的偏移量。偏移量本身在区间内部是连续的，因此从第一个元素到最后一个元素，只需要在区间起点告诉系统“从这里开始，每个人加上 c”，在区间结束的下一个位置告诉系统“到这里为止，恢复正常”。

差分数组的累加过程，其实就是把这个通知翻译成真实成绩的过程。每次操作都不直接改动所有目标元素，而是修改差分数组上的两个“开关”。最后统一扫描一遍，所有“开关”的效果自然落到每一个成绩上。这种正确性不依赖操作顺序，因为加法满足交换律和结合律，先加后加都不会改变最终结果。

4. 代码实现：C++ 参考模板与逐行解析

4.1 可提交的参考代码

下面是一份可以套用的 C++ 代码。为了保险，我使用了long long类型，因为成绩加次数多时，累加结果可能超过int范围。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<long long> a(n + 2, 0); vector<long long> diff(n + 3, 0); for (int i = 1; i <= n; i++) { cin >> a[i]; } diff[1] = a[1]; for (int i = 2; i <= n; i++) { diff[i] = a[i] - a[i - 1]; } for (int i = 0; i < m; i++) { int l, r, c; cin >> l >> r >> c; diff[l] += c; diff[r + 1] -= c; } long long ans = LLONG_MAX; long long cur = 0; for (int i = 1; i <= n; i++) { cur += diff[i]; if (cur < ans) { ans = cur; } } cout << ans << '\n'; return 0; }

这份代码在思路上没有任何花哨的东西，就是按照上面的步骤一步步实现的。如果你平时习惯用scanf/printf，也可以把输入输出替换掉，只要注意不要混用。因为代码里使用了ios::sync_with_stdio(false)，再混用scanf可能会让缓存出现问题，虽然很多环境能跑，但没必要给自己加风险。

4.2 代码里的关键细节

第一个细节是数组大小。我开vector<long long> diff(n + 3, 0)，多出的空间就是为了处理r + 1越界的问题。如果输入的 r 正好是 n，那么r + 1 = n + 1，数组必须有这个位置才行。多开一个位置是最稳的做法，不要吝啬这几个元素。

第二个细节是初始化。如果我用diff[1] = a[1]的方式构造，那么diff[2]到diff[n]都会在下面的循环中赋值为相邻差值。有些代码会偷懒写成diff[i] += ...，因为 vector 默认全 0，所以也可以直接累加。但是我觉得初学阶段写清楚比较好，不要让代码产生“这步到底是在覆盖还是累加”的疑问。

第三个细节是LLONG_MAX。如果题目保证成绩不会太大，用INT_MAX也可以。但区间加操作会导致最终成绩可能超过 2^31-1，使用long long始终更安全。统计最小值时，万一某次加了负数，答案可能为负，使用极大值初始化仍然正确。

4.3 复杂度和内存占用

时间复杂度方面，构造差分数组需要 O(n)，每条区间加法是 O(1)，m 条就是 O(m)，最后扫描还原又是 O(n)。总复杂度是 O(n + m)。相比暴力 O(nm)，效率提升非常明显。如果 n 和 m 都是 10^6，这个算法只需要百万级别的常数操作，轻松通过。

空间复杂度是 O(n)，主要用来存差分数组和初始成绩。网上有些代码只保留差分数组，可以把空间砍一半。但在竞赛环境里，O(n) 已经非常宽裕，没必要为了省一点空间牺牲可读性。如果遇到 n 特别大的题目，再考虑省掉a数组，逻辑完全一样。

5. 常见问题与排查技巧：差分题最容易踩的坑

5.1 典型问题速查表

我在给身边同学调试这道题时，发现大家出错的地方惊人的一致。下面整理成一张表格，方便你对照排查。

这张表基本覆盖了大多数“看起来能过小样例但一提交就挂”的情况。如果你发现自己的答案和样例一模一样，但拿到大数据就错，多半是数组容量或者整数溢出问题。

5.2 差分数组的边界与容量问题

因为区间加会访问d[l]和d[r+1]，所以l至少为 1，r+1最多为 n+1。数组如果只开到 n+1，访问d[n+1]还在范围内；但如果之后循环到cur += diff[i]时 i 只到 n，不会访问 n+1 以外。为了保险，我习惯统一开 n+2 或 n+3。

同样要注意的是，如果题目的 l 和 r 是从 0 开始编号的，把 0 换成 1 之后，r+1最大可能是 n，而不是 n+1，因为最大合法下标是 n-1 加 1 后成为 n。如果你直接把原始 l、r 代入公式，不做下标转换，结果必错。

5.3 读入方式与初始化易错点

很多初学者在关闭 C++ 输入输出同步后，混用cout和printf，结果输出顺序混乱。建议把整个代码统一为一种输入输出方式。用cin/cout时记得加上：

ios::sync_with_stdio(false); cin.tie(nullptr);

另外，检查差分数组是否初始化全零。如果用全局数组static，编译器会帮你清零。如果用vector，也需要明确指定0初始化。如果图省事开了局部普通数组，又没有手动清零，里面是随机值，结果会不可预料。

初始成绩的读入也很容易错。有些人会在读入a[i]的同时就把diff[i]置成a[i]，但后面构造差分时又跑了一个循环，这会导致重复赋值。我的建议是：要么先读a，再用循环构造diff，要么在读入时用累加的方式初始化diff，不要混用两种写法。

5.4 最小值统计的细节

统计最小值时，cur必须从 0 开始累加。因为在差分数组中，diff[1]已经包含了 a[1]，cur在累加diff[1]前是 0，累加后就是 a[1]。如果你把cur初始化为diff[0]，那就不对了，因为diff[0]是占位用的，不是真实成绩的一部分。

还有一种常见错误是在最终循环中用了for (int i = 0; i < n; i++)，但差分数组的下标是从 1 开始的，这样会把diff[0]加进去，导致第一个学生的成绩多出一个莫名其妙的值。这块务必注意：题目给定下标从 1 开始，代码也最好保持一致，尤其当你同时用到r + 1的位置时，1-based 最不容易搞乱。

6. 差分算法的延伸场景与个人实战体会

6.1 差分不只解决成绩题

P2367 看起来是一个“语文成绩”的小题，但它背后的差分思想出现在很多场景里。最常见的模拟场景是“公交车上下车人数”：每一站有人上车、有人下车，最后求总人数。把每个站点看作数组下标，上车就是区间起点加，下车就是区间终点减，处理所有事件后前缀和还原，就能知道每时每刻车上有多少人。

还有空调温度控制、任务调度、库存变化、活动时间段计数等，都可以抽象成区间加减。如果你已经熟练掌握一维差分，那么二维差分、树上差分、配合离散化的差分都会更容易理解。遇到“多次给一个区间的所有元素加同一个值，最后统一查询”这种描述，第一反应就应该是差分。

6.2 二维差分离散化等进阶方向

二维差分的思路和一维完全一致，只是把区间从一段变成一块。修改时需要在四个角上做加减，最后做两维前缀和。虽然代码比一维复杂，但理解了一维“起点加、终点减”的记号法，二维也可以类比上去。

如果题目中的区间端点不是连续存在，而是稀疏的大范围坐标，可以先把所有端点排序去重，用离散化后的下标再跑差分。这种技术在线段覆盖问题中很常见。不过这些都建立在透彻理解一维差分的基础上。把 P2367 吃透，等于给这些进阶内容打了一个非常扎实的底子。

6.3 我的实战体会与建议

做这道题最容易错的地方，其实是观念转换。很多人不敢用差分，是因为总觉得“没有经过每个学生，怎么知道他最终考了多少分”。但差分的美妙之处恰恰在于：你不需要知道每个中间状态，只需要在终点把所有偏移量一次性结算。就像发工资条，你可以只在工资变化时改一行记录，而不是每天重新打印所有人的工资明细。

我个人在带新手做这题时，最推荐的练习方式不是直接背模板，而是先手动做三组小数据。第一组只有一个区间操作，第二组有两个重叠区间，第三组有一个区间恰好到数组末尾。把这三组数据用纸笔模拟一遍，再对照代码，几乎不会再犯边界错误。如果你正在准备算法入门，刷到这道题时不要急着提交，先在草稿纸上把差分数组推一遍，体会一下“区间加 = 两次单点修改”的感觉。推明白之后，你会发现后面遇到类似区间问题，思路会顺畅很多。