今天想聊的是第 170 场双周赛的第二题，题目编号 3751，题名叫“范围内总波动值 I”。我看这场双周赛的讨论区时，发现好多人第一眼看到“波动值”三个字就往难题方向猜，什么差分、滑动窗口、方差、离散化都冒出来了。其实这道题的数学对象非常朴素：给定一个整数数组，每次查询给一个闭区间[l, r]，要算的是区间内部所有相邻元素差的绝对值之和，也就是把一段序列里上下起伏的幅度累计起来。它考的不是什么复杂数据结构，而是你能不能把“区间查询”快速翻译成“前缀和”，以及下标边界能不能一次写对。
这类题放在双周赛 Q2 的位置，难度属于“会的人 5 分钟写完，不会的人能卡半小时”。对新手来说，它的价值不在解法多华丽，而在于帮你打通一个高频思路：区间上的可累加统计量，第一反应都应该是前缀和。下面我从题目拆解、推导过程、代码实现、避坑清单到同类型扩展，完整过一遍，希望能帮你在下次遇到同类题时直接形成肌肉记忆。
1. 题目拆解：先把“波动值”这个数学对象定义清楚
1.1 相邻差绝对值是波动的原子单位
“波动”这个词在股票、信号处理、时间序列分析里经常出现，落到数组上，最自然的定义就是把相邻两个数的差的绝对值看成一次“跳变”。数组从前往后扫，每个跳变都记录一次，区间内所有跳变累计起来，就是总波动。
举个例子，nums = [3, 6, 8, 5]。相邻差分别是：
|6 - 3| = 3|8 - 6| = 2|5 - 8| = 3
如果查询区间[1, 3]，也就是子数组[6, 8, 5]，那总波动就是|8-6| + |5-8| = 2 + 3 = 5。注意这里不是max - min = 8 - 5 = 3，而是要把每一步的跳变都加起来。[1, 5, 1]这个数组的首尾差是0，但总波动是4 + 4 = 8，这就是“总波动”和“振幅”最本质的区别。
有的同学会问，题目为什么不直接给一个公式，非要叫“波动值”？我猜出题人就是想让你先做数学建模，把文字描述翻译成F(l, r) = sum(|a[i] - a[i-1]|), i = l+1 .. r。这一步没想通的人，后面看样例都会觉得奇怪。想通之后，这道题基本上就变成了“数组区间求和”，也就是前缀和的主场。
1.2 Q2 的位置意味着什么
双周赛的题目难度分布一般是 Q1 热身、Q2 简单到中等、Q3 中等、Q4 硬核。Q2 通常不会要求复杂的算法设计，但一定会埋一个“识别点”。这道题的识别点有两个：
- 你能看出来每个查询结果等于若干固定相邻差的求和；
- 你能把区间求和直接转换成前缀和数组的两个下标相减。
只要这两点看破，整个题就是二十分钟以内的活。如果看不破，试图在每个查询里现场扫一遍区间，在n和q都到10^5量级时就会超时。我经常跟朋友说，双周赛 Q2 其实是在考“肌肉记忆”：有些套路你练过一百次，赛场上根本不需要思考就能写出来，这道题就是典型。
2. 从暴力扫描到前缀和：推导过程中的关键思考
2.1 暴力做法的复杂度瓶颈在哪里
先写最直观的暴力。假设nums长度为n，查询次数为q，对于每次查询[l, r]，直接在循环里从l + 1遍历到r，累加绝对值：
ans = 0 for i in range(l + 1, r + 1): ans += abs(nums[i] - nums[i - 1])单次查询最坏要遍历O(n)个元素，总复杂度O(n * q)。当n = 10^5、q = 10^5时，最坏情况达到10^10量级操作，显然跑不动。就算题目给的时间比较宽，也没有人想在比赛里赌常数。
但这里有一个很重要的观察：abs(nums[i] - nums[i-1])是一个只跟i有关的固定值，它不会随着查询区间的变化而变化。也就是说，整个数组可以预先算出一份“相邻差数组”，然后问题就变成了：给定一个数组D，多次查询某个区间[L+1, R]的和。区间和怎么快速求？前缀和。
这个思路是不是很眼熟？它跟“给定数组，多次查询子数组和”完全同构。很多人被“波动”这个包装词带偏了，其实核心还是老朋友。
2.2 前缀和的推导与下标对齐
我们定义原始数组为a[0..n-1]。相邻差数组为：
d[i] = |a[i] - a[i-1]|, i = 1, 2, ..., n-1再定义前缀和数组s：
s[0] = 0 s[i] = d[1] + d[2] + ... + d[i]也就是s[i]表示从数组开头到第i个位置为止的所有相邻跳变累计值。注意，s的长度和原数组相同，都是n，其中s[0] = 0是因为下标0前面没有元素，自然没有跳变。
对于查询[l, r]，我们要的区间跳动是：
d[l+1] + d[l+2] + ... + d[r]用前缀和表示就是：
s[r] - s[l]这里特别容易混淆，很多人会写成s[r] - s[l-1]，那就多算了一个d[l]。我建议你记一个口诀：“左端不减自己，减的是左邻居”。因为d[l] = |a[l] - a[l-1]|这条跳变发生在l-1到l之间，它不在查询区间[l, r]内部，所以必须减掉。
验证一下刚才的例子，a = [3, 6, 8, 5]：
d[1] = 3, d[2] = 2, d[3] = 3 s[0] = 0, s[1] = 3, s[2] = 5, s[3] = 8查询[1, 3]，s[3] - s[1] = 8 - 3 = 5，和手工算的一致。如果错误地写成s[3] - s[0] = 8，就等于是把a[0]到a[1]的那次跳变也加进去了，显然不对。
2.3 复杂度对比
| 方案 | 预处理 | 单次查询 | 总复杂度 | 空间 |
|---|---|---|---|---|
| 暴力扫描 | 无 | O(len) | O(n * q) | O(1) |
| 前缀和 | O(n) | O(1) | O(n + q) | O(n) |
对于竞赛数据范围，前缀和方案是稳定的最优解。这里没有更复杂的做法，也不需要二分、线段树，因为它要统计的对象是完全线性的累加量，前缀和就是它的自然表达。
3. 代码实现与逐行注释
3.1 Python 参考实现
比赛里我一般直接用 Python 写，因为逻辑短，不容易出语法错。核心代码就是构建前缀和数组，再处理查询：
from typing import List def range_fluctuation(nums: List[int], queries: List[List[int]]) -> List[int]: n = len(nums) pref = [0] * n for i in range(1, n): pref[i] = pref[i - 1] + abs(nums[i] - nums[i - 1]) ans = [] for l, r in queries: ans.append(pref[r] - pref[l]) return ans解释一下关键点。
首先，pref的长度是n而不是n+1。因为pref[i]的语义是“从数组开头到第i个下标位置累计了多少跳变”，下标0对应“没有跳变”，所以pref[0] = 0。这样处理查询时pref[r] - pref[l]刚好就是跳变下标l+1到r这一段，思路非常通顺。
其次，构建过程中的abs(nums[i] - nums[i-1])是核心原子操作。nums里可能有负数、有相同元素、有极大极小值，但这一步只关心相邻差的大小，不关心方向，所以绝对值是必须的。
最后，ans.append(pref[r] - pref[l])对应一次查询。如果l == r，那么pref[r] - pref[l] = 0，逻辑上也是对的，因为区间里只有一个元素，没有任何相邻跳变。
3.2 C++ 实现与 64 位防溢出
C++ 写这道题要注意一点：结果可能超过int范围。假设数组长度是10^5，每个相邻差最大到10^9，那前缀和能达到10^14，绝对不是一个int能放下的。所以下面代码里pref和返回结果都用long long：
class Solution { public: vector<long long> rangeFluctuation(vector<int>& nums, vector<vector<int>>& queries) { int n = nums.size(); vector<long long> pref(n, 0); for (int i = 1; i < n; ++i) { pref[i] = pref[i - 1] + abs((long long)nums[i] - nums[i - 1]); } vector<long long> ans; ans.reserve(queries.size()); for (auto& q : queries) { int l = q[0], r = q[1]; ans.push_back(pref[r] - pref[l]); } return ans; } };这里有一个细节：我先做了(long long)nums[i] - nums[i - 1]再取abs，而不是直接abs(nums[i] - nums[i-1])。原因是两个int相减本身就可能溢出，比如-2147483648减2147483647，直接超过int能表示的边界。先转成long long再相减，安全得多。这种细节在力扣的测试数据里不一定能碰到，但在工程实践中绝对是基本素养。
3.3 Java 实现要点
Java 的思路和 C++ 几乎一样，注意Math.abs的参数类型。如果直接传int表达式，结果还是会先算int，存在同样的溢出风险。我习惯显式转long：
class Solution { public long[] rangeFluctuation(int[] nums, int[][] queries) { int n = nums.length; long[] pref = new long[n]; for (int i = 1; i < n; i++) { pref[i] = pref[i - 1] + Math.abs((long) nums[i] - nums[i - 1]); } long[] ans = new long[queries.length]; for (int i = 0; i < queries.length; i++) { int l = queries[i][0]; int r = queries[i][1]; ans[i] = pref[r] - pref[l]; } return ans; } }可以看到，三种主流语言的逻辑完全一致。你只要在脑子里建立一个“前缀和数组 = 跳变累计值”的模型，写哪个语言的版本都不会错。
4. 边界情况与避坑清单
4.1 最容易踩的下标坑
这道题的大部分 bug 都出在下标上。我整理了几个真实比赛里常见的错误写法：
| 错误写法 | 错误后果 | 正确写法 |
|---|---|---|
pref[r] - pref[l - 1] | 多算了一次d[l]，答案偏大 | pref[r] - pref[l] |
用pref[l+1]当左边界 | 漏算了左端点本身需要的跳变 | pref[l] |
构建时从i = 0开始 | pref[0]变成无意义值 | 从i = 1开始 |
返回int数组 | 数据大时溢出 | 返回long long/long[] |
为了加深记忆，我再推一遍。你要统计的是[l, r]内部的相邻跳变，跳变的下标范围是l+1到r。前缀和pref[r]包含了d[1]到d[r]的全部累计值，pref[l]包含了d[1]到d[l]的全部累计值。两者相减，剩下的正好是d[l+1]到d[r]，一个不多一个不少。这是一个“左闭右开”思想在具体场景里的应用，只是它表现成了“左端点不减自己、减的是左邻居”。
4.2 查询区间为空或者只有一个元素
如果查询给出[l, r]，其中l == r，区间里只有一个元素，不存在相邻跳变，答案就是0。用pref[r] - pref[l]计算，会自动得到零，所以不需要特判。这一点有时反而会迷惑人：看到返回 0 以为是自己写错了，其实是对的。
如果数组长度为 1，那么pref数组长度也是 1，pref[0] = 0。随便来多少查询，结果都是 0。有的同学会在构建循环里写成for i in range(1, n+1)，然后访问nums[i]，当n = 1时直接越界。这个要小心。
4.3 负数和重复元素
负数不会影响计算，因为两边都套了绝对值，差的符号翻不翻无所谓。重复元素和相邻相同的情况会产生0，对前缀和没有副作用。
但我见过有人试图优化：先判断a[i] > a[i-1]再减，写出一大堆分支。完全没有必要，绝对值的开销微乎其微，别为了省一个函数调用把自己的逻辑搞复杂。这种过度优化在竞赛里是大忌。
4.4 大数溢出
这个问题前面已经提过，但值得单独列出来。nums[i]可能是10^9量级，n可能是10^5，pref的累加值完全可能超过 32 位整数的上限。如果不提前用long long，最后几个测试用例会给你一个莫名其妙的负数答案，而你排查半天都找不到原因。我的经验是：只要题目里的数组长度和元素范围相乘可能超过2^31，就无脑用 64 位，不要在赛场上赌运气。
5. 这类题还能怎么变着考：同源扩展与思路迁移
5.1 变形一：让你统计所有子数组的总波动之和
我知道有的读者看到“范围内总波动值 I”会觉得后面肯定还有“II”，所以会好奇：如果题目再难一点，应该怎么考？
一种非常自然的升级方式是：不再给你查询区间，而是让你直接求整个数组所有连续子数组的总波动之和。这时候暴力枚举子数组是O(n^2)的，需要换个角度。一个相邻跳变d[i] = |a[i] - a[i-1]|，会被多少个连续子数组覆盖？只要子数组的左边界在0..i中取值，右边界在i..n-1中取值，就会包含它。所以贡献次数是：
(i + 1) * (n - i)注意这里边界是“包含下标i-1和下标i这一对相邻元素”，所以左边界有i种选择，右边界有n - i种选择，总数就是i * (n - i)。细心一点，把下标从 0 开始对号入座。最后答案就是：
sum(d[i] * i * (n - i)), i = 1..n-1这种“统计每个元素对多少个区间有贡献”的方法，叫贡献法，是前缀和之后很自然的进阶思路。如果“II”出在这种方向，我一点都不意外。
5.2 变形二：查询范围变成了子区间套娃
另一种考法是把查询范围本身再扩大一层：给你一个区间[L, R]，要你求这个区间内所有连续子区间各自总波动之和。这时候每个相邻跳变d[i]的贡献次数变成：
(i - L + 1) * (R - i)前提是i在[L+1, R]范围内。如果i在这个范围外，贡献为 0。这个式子只需要预处理相邻差，再配合前缀和就能做到单次查询O(1)，因为乘法和累加都可以拆成关于i的多项式。这种题看起来复杂度上升，实际上还是前缀和和贡献法的排列组合。
5.3 变形三：如果官方把“波动值”定义成最大值减最小值
这里必须提醒一下：做题时第一件事永远是确认题目定义。如果某个版本把“波动值”定义成了一个区间内max - min，而不是相邻差绝对值之和，那么上面整套前缀和方案就不适用了。范围最值查询需要另一套工具，比如稀疏表或线段树。
但 3751 这道题从题目名字里的“总波动”三个字来看，强调的是累计，不是振幅。而且 Q2 的难度也不太可能让你在赛场上手写稀疏表。所以我个人判断，正确的定义就是相邻差绝对值之和。当然，如果你在考场上拿到的题目表述有歧义，一定要以题目给出的公示或样例为准。
5.4 竞赛节奏建议
这种 Q2 题，我建议的节奏是：读题 1 分钟，建模 2 分钟，写代码 5 分钟，检查边界 2 分钟。总耗时控制在 10 到 15 分钟以内。如果你在“波动值”三个字上纠结太长时间，说明平时积累的数学模型还不够多。我自己的习惯是，看到“区间”、“每次查询”、“总和”这几个词同时出现，直接先写前缀和模板，再去核对定义细节。这样既快又稳，还能省下时间给后面的 Q3、Q4。
另外，写完代码后别急着提交，先拿题目样例手工跑一遍。这个样例一般都会覆盖普通情况，但不会覆盖l == r和单元素数组这种边界。我会额外加一个长度为 1 的自测用例，确保不越界。这种做法看着很小，但在竞赛里能帮你省下一次罚时。
最后分享一点个人体会。我最早做区间类题目时，也经常在-1和+1之间反复横跳，后来发明了一个办法：每次写完前缀和代码，先把数组在草稿纸上画成一个个格子，每个格子之间标上差值，然后再看查询区间到底跨越几条“差值边”。图像一旦清晰，下标自然就不会错。这个方法听起来幼稚，但实际非常管用。希望你在做这道题的时候，也能找到属于自己的那个“下标校验锚点”。
