增减序列题解：差分数组如何将区间操作转为端点操作

说真的这道“增减序列”我前后刷了三遍。第一遍觉得懂了关上题解自己写卡在第二个答案上出不来第二遍背了结论没过多久又忘直到第三遍把所有推导过程在草稿纸上完整走了一遍才算真正把它吃透。今天这篇文章就把它从头到尾掰开揉碎包括为什么第一次看到题要往差分数组上想、第一个答案为什么一定是正负差分绝对值的最大值、第二个答案为什么是差值加一以及我在实际写代码时踩过哪些坑。看完你不仅能AC这一道题还能顺手搞定一批同类区间操作问题。1. 增减序列的题意拆解核心是把“区间”变成“点”1.1 题目到底说了什么关键限制在哪里这道题给了一个长度为 n 的整数序列允许做的操作只有一个每次选择一个连续区间 [l, r]把这个区间内所有元素同时加 1 或者同时减 1。问两件事第一件是最少需要多少次操作能让整个序列的所有元素变成同一个值第二件是在保证操作次数最少的前提下最终能得到多少种不同的目标值。这里有几个限制条件特别容易忽略。第一区间必须是连续的不能跳着选元素第二每次操作只能整体加一或整体减一不能一部分加一部分减第三区间长度没有下限要求所以你可以选一个长度为 1 的区间也就是单点操作。这三个条件合在一起决定了这个问题不能用普通贪心直接蒙答案。很多初学者看到这种题会本能地想去模拟每次找到最大值和最小值然后对中间这段做调整让它们慢慢靠拢。理论上这个思路方向没错但问题在于区间操作会把大量元素捆绑在一起你调整一次可能让一部分元素变好了同时又让另一部分变差了全局状态根本没法用一个简单的指标来描述。暴力回溯更不现实序列长度轻松上万每次操作的位置和方向组合多到爆炸。我最初也尝试过贪心模拟写了差不多一百行跑小样例勉强对一提交就是超时或者答案错误。原因很简单直接对原数组做操作信息量太大了每走一步都要考虑整个数组的状态。这道题真正的突破口在于换一个视角不要盯着每个元素的值看改成看相邻两个元素的差值。所有元素相等这件事用相邻差值的语言来说就是所有差值都变成 0而这一下就把问题从“一个整体区间”简化成了“一堆独立的差值关系”。1.2 从结果反推关注“相邻差”而不是“绝对值”举个例子序列 [3, 1, 5, 4, 2] 看起来没什么规律但如果转换成相邻差值就是 a2-a1-2a3-a24a4-a3-1a5-a4-2。我们的目标是让整个序列变成一个常数比如 [5, 5, 5, 5, 5]那么对应相邻差值就是 0, 0, 0, 0。所以问题等价于通过区间加减操作把这些相邻差值全部消成 0。为什么这个视角好因为原始数组的每个元素都跟一堆邻居纠缠在一起改动一个元素会影响至少两个差值。但如果我们只看差值数组一次区间操作在差值数组上产生的变化其实非常有限几乎只涉及两个位置。这就是差分数组登场的理由。不用急着理解这句话下一节我们具体拆开看。2. 差分数组是这道题的题眼一次区间操作只有两个点会变化2.1 差分数组的定义和直觉理解差分数组说起来不复杂。给定原数组 a从下标 1 开始定义 d[i] a[i] - a[i-1]其中 i 从 2 到 n。有些教材还会额外定义 d[1] a[1]这样整个数组 a 就可以通过差分数组的前缀和还原出来a[k] d[1] d[2] ... d[k]。你可以把差分数组理解成“地势的坡度”。原数组是每一站的海拔高度差分数组就是相邻两站之间的坡度。海拔高不代表坡度大坡度大也不代表海拔高这两个视角各有各的作用。当我们关心“整体升到同一高度”这类问题时坡度显然比海拔更直接全部站点海拔一样等价于所有坡度为零。我自己更习惯用 d[1] 保留 a[1] 的写法这样分析边界情况时特别清晰因为 d[1] 恰好就是最终目标值。比如 [5, 2, 2] 这个数组差分就是 d[1]5d[2]2-5-3d[3]2-20。要让所有数相等其实就是让 d[2] 和 d[3] 都变成 0而 d[1] 自然就是所有元素最后变成的那个值。2.2 区间加一减一在差分数组上长什么样这是整个题最核心的翻译工作。假设我们对区间 [l, r] 整体加 1那么这会导致 a[l] 比 a[l-1] 相对变大了 1同时 a[r1] 比 a[r] 相对变小了 1。反映到差分数组上就是 d[l] 加 1d[r1] 减 1。如果 r 恰好是 n那么 d[r1] 不存在只有 d[l] 加 1。区间整体减 1 的情况正好反过来d[l] 减 1d[r1] 加 1。这个性质太关键了。一次原本影响整个区间所有元素的操作在差分视角下只动了两个点甚至有时只动一个点。这就把一个“互相牵扯的大问题”变成了“一对一点名的小问题”。举个例子对 [2, 3] 区间执行加 1原数组 [3, 1, 2] 变成 [3, 2, 3]你直接看差分d[2] 从 -2 变成 -1d[3] 从 1 变成 1d[4] 不存在所以不用管。对不对再验证一下另一个端点的变化确实只有两个差分位置发生了改变。这种“区间操作降维成端点操作”的思路就是差分数组在区间问题里反复出现的原因。所以要达到最终状态“所有数相等”差分数组上要满足的条件就变得极其干净从 d[2] 到 d[n] 全部清零d[1] 爱是多少是多少因为 d[1] 就是那个共同值。2.3 为什么 d[1] 是自由的但也是最容易想岔的地方很多人到这一步就会有个疑问既然目标只是把 d[2..n] 清零那是不是所有操作都可以避开 d[1]操作次数当然可以但问题问的是“在最少操作次数下有多少种目标值”这就要看剩余的操作能不能顺带改变 d[1]而且不增加总次数。这个细节正是第二个答案的来源。从操作对差分的影响看能碰到 d[1] 的操作只有一种选择左端点为 1 的区间 [1, r]。比如 [1, r] 区间加 1会让 d[1] 加 1同时 d[r1] 减 1。如果这个 d[r1] 恰好是一个需要减掉的正数那这次操作就一举两得既完成了一次“配对”又改变了最终目标值。这就是方案数推导的核心契机。先记住这个伏笔后面我们会在推导部分把它彻底展开。3. 关键推导最少次数为什么是 max(pos, neg)方案数为什么是 abs(pos-neg)13.1 统计正差量和负差量现在把问题纯化成这样我们有若干位置每个位置 d[i]i 从 2 到 n有一个初始值正数代表“过头了”需要减负数代表“不够”需要加。定义一个正差总量 pos等于所有正数 d[i] 的和再定义一个负差总量 neg等于所有负数绝对值的和。比如前面提过的 [5, 2, 2]d[2] -3d[3] 0所以 pos 0neg 3。再比如 [1, 2, 3]d[2] 1d[3] 1所以 pos 2neg 0。这两个例子都很极端但正好能说明两种不同的局面正差多还是负差多。从“需求量”的角度看所有正的位置总共需要被削减 pos 次所有负的位置总共需要被填补 neg 次。每进行一次区间操作在差分上要么同时影响两个位置要么只影响一个位置。如果是同时影响理想情况下可以让一个正的位置减 1同时让一个负的位置加 1这样一次操作同时完成两件事如果只影响一个位置那就只能完成一件事。清楚了这一点操作次数的下界就很容易逼近了。3.2 配对操作一次处理两个端点剩下的只能单独处理假设存在一个操作它同时让某个正差分减 1又让某个负差分加 1那么它一次就消灭了两个单位的“偏差”。这种操作最多能做多少次最多 min(pos, neg) 次因为正偏差总量只有 pos负偏差总量只有 neg两者无论哪个先耗尽配对就结束了。做完这些配对之后剩下的偏差量是 |pos - neg|。这时候已经没有异号的偏差可以配对了剩下的所有偏差都是同号的只能靠“单端点”操作来处理。什么是单端点操作就是选择区间 [l, n] 或者 [1, r]让右端点或左端点落在数组边界上这样差分数组只在 l 或 r1 这个位置发生变化没有对端。于是最少操作次数 配对次数 单独处理次数 min(pos, neg) |pos - neg|。这个式子稍微整理一下就是 max(pos, neg)。如果你愿意也可以从下界来证明因为正偏差总量是 pos而每一次操作最多只能让正的偏差减少 1所以至少要操作 pos 次同理负偏差总量是 neg每次操作最多只能让负偏差的绝对值减少 1所以至少要操作 neg 次。两个下界同时成立那么操作次数不可能少于 max(pos, neg)。而刚刚的“配对加单处理”构造方案正好达到了这个次数所以最少操作次数就是 max(pos, neg)。这个推导我第一次看的时候觉得太简单第二次自己推的时候才意识到关键是必须想清楚“每次操作减少一个单位的正偏差”和“每次操作减少一个单位的负偏差”这两个约束是并列的不是可以相互替代的。一个操作同时减少正偏差和负偏差时它同时满足了两边的下界所以能达到最优。这个逻辑是整道题的灵魂。3.3 方案数推导多出来的操作怎样影响第一个差分值第二个问题稍麻烦。关键结论是如果 pos 大于 neg说明正偏差多剩下 |pos - neg| 次操作是在“削减正偏差”。如果 neg 大于 pos说明负偏差多剩下 |pos - neg| 次操作是在“填补负偏差”。如果 pos 等于 neg那所有操作都能配对d[1] 永远不会被额外影响最终目标值只有一种。先看 pos neg 的情况。剩下的正偏差要削减标准做法是选择区间 [l, n] 做减 1这样只会让 d[l] 减 1不会碰到 d[1]。但如果你把其中某些次操作改成选择区间 [1, r] 做加 1结果会怎么样这个加 1 操作会让 d[1] 加 1同时让 d[r1] 减 1而 d[r1] 恰好可以选成那个需要削减的正偏差位置。换句话说你照样削减了一个单位的正偏差没有增加操作次数但额外让最终的共同值变大了 1。所以在这 |pos - neg| 次剩余操作里你可以选择 0 次、1 次、2 次……一直到全部这么干对应最终目标值从初始 d[1] 一直变大到初始 d[1] (pos - neg)一共 |pos - neg| 1 种。再看 neg pos 的情况逻辑镜像倒过来。剩下的负偏差要填补标准做法是选择 [l, n] 做加 1只影响 d[l]。但如果你把其中某些次操作改成选择区间 [1, r] 做减 1这个减 1 会让 d[1] 减 1同时让 d[r1] 加 1而 d[r1] 正好可以选成那个需要填补的负偏差位置。这样同样没有增加操作次数但让最终共同值变小了 1。选择 0 次到 |neg - pos| 次这么做最终目标值从初始 d[1] 一直减小到初始 d[1] - (neg - pos)一共 |neg - pos| 1 种。两种情况合并方案数就是 abs(pos - neg) 1。这个式子简洁归简洁但如果没有想明白“多出来的操作可以拿边界区间去换 d[1] 的变化”光背结论是很容易在考试或者面试追问下露怯的。因为我第一次就是死记的结论被朋友问了一句“为什么不是 abs(pos-neg)”就卡住了。这里的 1 本质上代表“一次都不改变 d[1]”的那个方案永远不能漏掉。3.4 用两个小例子把结论砸实光说理论不落地容易飘我建议拿到这个结论后立刻手推两个极端例子。先看 [5, 2, 2]。差分 d[2]-3d[3]0pos0neg3。按照公式最少操作次数 max(0,3) 3方案数 |0-3| 1 4。这四种目标值是按初始 d[1]5 往下走的5, 4, 3, 2。验证一下目标为 4 的情况从 [5,2,2] 出发第一步对 [1,1] 减 1 变成 [4,2,2]第二步对 [2,3] 加 1 变成 [4,3,3]第三步再对 [2,3] 加 1 变成 [4,4,4]正好三步。目标为 2 的情况更简单对 [1,1] 减 1 三次直接变 [2,2,2]。确实是最少三次。再看 [1, 2, 3]。差分 d[2]1d[3]1pos2neg0。按照公式最少操作次数 max(2,0) 2方案数 |2-0| 1 3。这四种不是三种目标值按初始 d[1]1 往上走1, 2, 3。目标 2 的构造很有意思先对 [1,1] 加 1 变成 [2,2,3]再对 [3,3] 减 1 变成 [2,2,2]正好两步。目标 3 也可以两步先对 [1,2] 加 1 变成 [2,3,3]再对 [1,1] 加 1 变成 [3,3,3]。这两个例子一个往下走一个往上走方向正好相反强烈建议你在草稿纸上亲手画一遍差分的变化过程。3.5 参考代码实现注意类型、下标和方向推导清楚了代码其实很短。我的建议是直接用 long long不要用 int原因后面说。#include iostream #include vector #include cmath using namespace std; int main() { int n; cin n; vectorlong long a(n 1); for (int i 1; i n; i) { cin a[i]; } long long pos 0, neg 0; for (int i 2; i n; i) { long long d a[i] - a[i - 1]; if (d 0) pos d; else neg -d; } cout max(pos, neg) \n; cout abs(pos - neg) 1 \n; return 0; }Python 版本的逻辑完全一样n int(input()) a list(map(int, input().split())) pos 0 neg 0 for i in range(1, n): d a[i] - a[i - 1] if d 0: pos d else: neg -d print(max(pos, neg)) print(abs(pos - neg) 1)这里最关键的一行代码就是差分并分类累加。注意循环从 i2 到 n对应 d[2] 到 d[n]也就是说差分数组的第一个位置 d[1] 不参与统计。这个下标细节我至少看漏过两次一旦循环写错样例可能碰巧过但一提交就暴露。还有每道题如果 a 的范围给到 1e9、n 给到 1e5差分值累加起来的量级能到 1e14int 是绝对装不下的long long 是底线。4. 实操中的坑与差分数组的扩展玩法4.1 我踩过的几个坑类型、下标、方向第一个坑就是类型。很多人觉得差分数组里的值也就是差个几百几千没必要用 long long。但你想一下如果一个区间很长你反复对它加一原数组的值可以被推到很大差分虽然只反映相邻两个数的差但累加和可能极其夸张。最坏情况下 n 万级别、每项绝对值 1e9差分累加可以超过 2^31。反正我在 C 里用 int 被教育过一次之后就长记性了凡涉及求和直接上 long long省得后续 debug。第二个坑是负数的统计方向。差分值为负数时比如 d -5你要累加的是它的绝对值 5 到 neg 里去而不是把 -5 直接加进去。这个错误很隐蔽因为样例数据如果恰好正负抵消输出也能对上。我见过不少人在这一步写成了 neg d结果 pos 和 neg 一正一负算出来的 max 完全没意义。写的时候记住一句话pos 是“正偏差的总量”neg 是“负偏差的总量”总量永远是正数。第三个坑是方案数忘记取绝对值再 1。abs(pos - neg) 1这个 1 特别好忘特别是有一次我对着样例百思不得其解为什么正确答案比我算的多 1后来才意识到自己默认了“必须至少操作一次改变 d[1]”的错觉。实际上“一次都不改变 d[1]”完全合法而且就是最优解里的一种所以必须 1。第四个坑是方向感。正差多时最终目标值会从初始值往上走负差多时最终目标值会往下走。这个方向我第一次完全记反了当时拿 [5,2,2] 验证算出四种种数理所当然地猜是 5,6,7,8结果构造半天构造不出来。后来才意识到初始值为 5 且负差多剩余填补操作如果把某些次改成 [1,r] 减 1目标值是往 4、3、2 走的。建议你一旦记混就拿一个极端例子秒算比如 [5,2,2] 这种手推一步就明白了。4.2 差分数组还能这样用同类问题迁移思路这道题的价值远不止于本身 AC。差分数组处理“区间统一加减”类问题几乎是一个通用模板。比如给你两个序列 A 和 B每次可以把 A 的某个区间整体加一或减一问最少多少次能让 A 变成 B。这时候你先做一个逐项差分 A-B然后问题就回到了完全一样的模型把差分数组从第二个位置到第 n 个位置全部清零。所以一旦理解了增减序列这道变体题就是白送。另外一类常见变体是统计“区间加等差数列”或者“区间乘常数”之类的问题比如区间加一个首项为 x、公差为 y 的等差数列这种操作在普通差分数组上体现为两个位置各加一个数在二阶差分上体现为三个位置发生变化。核心思路同根同源把对区间的影响转换成差分数组上有限个端点的影响然后问题就变成了处理少数几个点的值。还有竞赛里常见的树上差分处理“树上一条路径所有点加一”这种操作。路径在树上不是连续区间但可以从某个端点出发做两次差分标记在 LCA 附近做额外处理本质还是把路径操作拆成若干点上的标记。树上的“区间”和数组里的区间长得不一样但思维模式是一样的想办法把范围操作降维成点操作最后用前缀和还原。4.3 学习建议什么时候该想到差分最后一个很实际的问题也是初学者最想知道的我怎么才能在看题的时候就想到差分数组我的经验有三个信号。第一题目里明确说了“选择一个连续区间整体加减同一个数”这种措辞基本就是差分题型的敲门砖。区间统一修改天然和差分数组的端点变化对应。第二题目问的是“全部变成同一个值”或者“变成目标序列”这类结果导向的问题。这时候相邻差值比绝对值更接近问题的本质。第三n 的范围通常很大大到没法做区间更新模拟但又没大到需要什么高深数据结构这时候差分往往就是那个“把 O(n) 操作降成 O(1) 更新”的利器。当然也不是所有区间操作题都用差分。如果操作次数很少、每次都要求查询区间最值那只靠差分是不够的需要线段树或树状数组。但如果操作是“统一加减”且最后只要整体结果差分数组就是最舒服的发力点。我的习惯是拿到题目先看操作类型区间统一加减优先想差分这能省下大量试错时间。结尾这道题我后来再去刷的时候基本闭着眼睛就能写出来但我依然觉得它的价值不在代码本身而在那个“把区间想成两个点”的思维转换。如果你第一次做没想通方案数为什么是 abs(pos-neg)1别急着背找几个小例子亲手推一推尤其是边界例子比如所有数相等、只有正差、只有负差这三类情况。推明白一次之后你会发现这个结论会牢牢长在你的脑子里而不是临时背下来的。最后再多说一句差分数组的套路值得花一个下午彻底搞懂因为后面遇到区间加减、树状数组、树上差分你都会反复和它重逢。