区间和转前缀和之差：USACO Range Reconstruction构造全解

做 USACO 的 Range Reconstruction 这题，最关键的一步就是把“区间和”四个字翻译成“前缀和之差”。这句话读起来很简单，但真到了考场上，很多人会被那个上三角矩阵唬住，以为要解方程组、甚至去搜回溯。实际上，这就是一道典型的“已知若干差值，反推坐标”的构造题，用前缀和做中轴，十几行代码就能结束战斗。

这个题适合想练“前缀和构造”手感的人看，也适合正在刷 USACO Silver 或洛谷普及+ 的选手。我会把题目怎么读、自由度怎么找、边界怎么处理、以及我在调试过程中踩过的几个坑全部摊开讲，保证你合上文章之后自己能把代码写出来。

1. 先认清题目给的牌：区间和到底约束了什么

1.1 题目在问什么

题意可以浓缩成一句话：有一个长度为 n 的整数数组 a，现在你知道所有长度至少为 2 的连续子段和，也就是对于任意 1 ≤ i < j ≤ n，都知道 a[i] + a[i+1] + … + a[j] 的值，让你根据这些信息构造出任意一个满足条件的原数组 a。

注意“长度至少为 2”这个条件。这是整道题最容易忽略，也是最关键的地方。因为这意味着你没有拿到任何单点元素的信息，拿到的都是“一段连续元素加起来等于多少”。

举个例子。假设真实数组是：

a = [1, -2, 3, 4]

那么你拿到的区间和会有这些：

[1,2] = -1
[1,3] = 2
[1,4] = 6
[2,3] = 1
[2,4] = 5
[3,4] = 7

注意里面没有 a[1]=1、a[2]=-2 这类单个元素的值。这就是题目的全部输入。

1.2 为什么不能直接当方程组硬解

第一次看到这种题目，直觉是列方程组。n 个未知数，已知 n(n-1)/2 个方程，看起来信息冗余得很，直接高斯消元不就行了？

理论上可以，但没必要，而且很容易把自己绕晕。原因有两点。

第一，这个方程组并不是满秩的。n=2 的时候，你只有 1 个方程，却有 2 个未知数，比如 a1+a2=5，那答案有无穷多个。n=3 的时候，有三个区间和：[1,2]、[1,3]、[2,3]，三个方程三个未知数，刚好能唯一解出 a。也就是说，随着 n 的增大，方程组的自由度甚至会发生变化。用高斯消元去处理一个可能欠定的符号方程组，远不如想清楚“哪些值是自由变量”来得干脆。

第二，题目要求的是“构造”，不是“求解唯一答案”。这意味着你只要给出一个合法数组就行，天然允许你主动设某个变量为 0 或任意值。这种自由度在搜索和暴力的思路里根本体现不出来，但在前缀和的视角下会非常清爽。

1.3 数据规模暗示了什么

这题的输入是完整的 n(n-1)/2 个区间和，所以数据规模不可能太大。n 大概在几百这个量级以内，总输入量是 O(n²)。这意味着你不可能用 O(n³) 的高斯消元去莽，也不需要用任何高级数据结构。

真正的难点不在数据规模，而在“挑出有用信息”。所有区间和都给你了，但大部分是冗余的。你要做的不是把冗余保留下来，而是从里面找出几条关键等式，把整个前缀和数组重新“撑”起来。

打个比方：给你很多城市之间的路距，让你把所有城市的地图画出来。有人会拿所有距离去建模，其实你只需要选出几段主路，把地图骨架搭好，其余数据用来验证就够了。

2. 前缀和是这类题的“翻译机”

2.1 一个记号，五分钟看懂

设前缀和数组 pre，其中：

pre[i] = a[1] + a[2] + … + a[i]

约定 pre[0] = 0。那么对于任意区间 [i, j]，都有：

sum(i, j) = pre[j] - pre[i-1]

这个式子就是整道题的题眼。

理解它可以用一个生活类比：你在一段路上每隔一段位置立一个里程牌，pre[i] 就是第 i 块里程牌上的读数。区间和 sum(i, j) 不是别的，就是第 j 块牌和第 i-1 块牌读数之差。

所以题目给你所有区间和，本质上是给你一大堆“两块里程牌之间的读数差”。你要做的，是给每一块里程牌定一个读数，使得所有已知差值都能对上。

2.2 把矩阵看成一张“差值图”

把每个已知区间和都看成一条无向边，连接两个节点，边权就是差值。继续用前面的例子：

a = [1, -2, 3, 4]

节点是 pre0 到 pre4。区间 [1,2] 就对应 pre2 - pre0 = -1，也就是一条连接节点 0 和节点 2、权值为 -1 的边。

把所有区间和写进表格，长这样：

所有区间和加起来，就形成了一张节点从 0 到 n 的差值图。每个节点表示一个前缀和，每条边的权值表示两个前缀和的差。

这个模型最大的优点是：它把“数组重建”问题彻底转化成了“给图上的节点定坐标”问题。你可以完全忘掉原数组，专心看这张图。

2.3 为什么差值图这个视角很重要

差值图里有一个非常朴素但有用的结论：每个连通块内部的所有节点，相对位置已经被完全确定，但整个连通块可以整体平移。

换句话说，如果一张图里只有一条边“pre2 - pre0 = 5”，那么 pre0 取 0、pre2 取 5；但也可以 pre0 取 100、pre2 取 105。节点之间的差不会变，数组 a 也不会变，变的只是整体加了一个偏移。

放到这题里，n 比较大的情况下，所有节点其实连成了一个连通块，所以整张图只有一个整体偏移自由度。我们只需要人为把 pre0 或某个节点固定为 0，所有其他前缀就全定了。

这个观察能帮你理解为什么这题是“构造”：如果你把 pre0 固定成 0，得到的是一个合法解；把 pre0 固定成 100，得到的是另一个等价解。题目只要任意一个，所以你可以随便挑一个舒服的固定方式。

3. 核心推导：如何把每一个前缀都“安放”好

3.1 能直接确定的：pre[2] 到 pre[n]

既然差分图已经建立，下一步就是选定一个参考点。

我习惯把 pre0 固定成 0。因为这样一来，所有形如 [1, j] 的区间和都直接变成了 pre[j] - pre0，也就是 pre[j]。

所以对于任意的 j ≥ 2，都有：

pre[j] = sum(1, j)

这是一个非常舒服的结论。只要把输入的第一行区间和拿出来，就能一口气确定从 pre2 到 pren 的所有前缀和。

还是用例子验证。已知 sum[1][2] = -1、sum[1][3] = 2、sum[1][4] = 6，于是：

pre2 = -1
pre3 = 2
pre4 = 6

这里有读者会问：pre1 去哪儿了？这正是下一步要处理的缺口。

3.2 最后一个缺口：pre[1] 的“绕路”解法

pre1 等于 a1，而在题目里没有任何一个区间和是直接告诉你 a1 的。你手里所有的区间，长度至少为 2。

但是我们有一条区间 [2,3]，它对应：

sum(2, 3) = pre3 - pre1

pre3 刚才已经求出来了，那 pre1 立刻就能解出来：

pre1 = pre3 - sum(2, 3)

结合之前得到的 pre3 = sum(1, 3)，等价于：

pre1 = sum(1, 3) - sum(2, 3)

用真实数据算一遍就是：pre1 = 2 - 1 = 1，刚好等于 a1。

这波“绕路”其实很典型。本质上你是在用两个大区间去反推一个单点值：sum(1,3) 是 a1+a2+a3，sum(2,3) 是 a2+a3，两者相减，自然得到 a1。这里的关键是，你手上虽然没有直接给 a1 的区间，但可以通过两个区间的差把它“挤”出来。

3.3 n=1 和 n=2 的边界，必须单独处理

看到这里，细心的读者会发现一个隐患：上面的公式用到了 sum(2,3)，前提是 n ≥ 3。如果 n 只有 1 或 2，情况会完全不一样。

n=1 的时候，没有任何长度至少为 2 的区间。你可以直接输出任意一个数，比如输出 0，因为你的数组就只有一个元素，没有任何约束，随便填。

n=2 的时候，你只知道 sum(1,2) = a1 + a2，两个未知数，一个方程。此时自由度为 1，随便给 a1 赋一个值，a2 就确定了。最省事的做法是令 a1 = 0，那么 a2 = sum(1,2)。

在实现时，这两个特判经常被人忽略。尤其是 n=2，如果直接套用 n≥3 的公式，会用到一个根本不存在的 sum(2,3)，结果不是数组越界就是得到一堆乱码。

3.4 为什么这样构造一定合法

有人会担心：我只用了第一行的区间和，以及一条 [2,3] 的信息，剩下那么多区间和没用上，构造出来的数组真的能满足所有输入吗？

答案是能，前提是题目保证输入来自某个合法数组。因为所有区间和并不是独立给出的，它们之间天然满足一致性。你从第一行和 [2,3] 推出 pre 数组之后，任意一个区间 [i,j] 的等式 pre[j] - pre[i-1] 会被自动满足。

这里可以做个反向验证。假设你构造出的 a 数组是 [a1, a2, ..., an]，那么任意区间和 sum(i,j) 等于 a[i] + … + a[j]，这是由前缀和的定义天然保证的。也就是说，只要你在构造时保证 pre[j] - pre[i-1] 对每个给定区间都等于输入值，输出 a 就一定正确。

实际竞赛中，你甚至可以加一个 O(n²) 的校验循环，把所有输入再查一遍。虽然正常情况下不会出问题，但这个习惯能在前几发提交把你从 WA 的边缘拉回来。

4. 代码实现与一处容易被带偏的写法

4.1 最直接的公式法代码

比赛里我一般写公式法，代码非常短。

#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<vector<ll>> sum(n + 1, vector<ll>(n + 1, 0)); for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { cin >> sum[i][j]; } } if (n == 1) { cout << 0 << '\n'; return 0; } vector<ll> pre(n + 1, 0); // pre[0] 固定为 0 for (int j = 2; j <= n; j++) { pre[j] = sum[1][j]; } // 补上 pre[1] if (n >= 3) { pre[1] = pre[3] - sum[2][3]; } // n == 2 时 pre[1] 保持 0，a1 = 0，a2 = sum[1][2] for (int i = 1; i <= n; i++) { cout << pre[i] - pre[i - 1] << " \n"[i == n]; } return 0; }

这段代码有几个关键点需要解释。

第一，读入时只读 i < j 的格子，不读对角线。因为题目只给了长度至少为 2 的区间和。我们平时读二维数组习惯了连对角线一起读，这里必须忍住。

第二，pre[1] 在 n≥3 时是用 sum(2,3) 补的。如果你换成别的构造方式，比如令 pre1 为任意一个数，也能输出合法答案，但用 sum(2,3) 补是信息最自然的选择。

第三，输出时直接用 pre[i] - pre[i-1]，算出每一项 a[i]。这个输出方式比记住一个个单独算要稳得多，因为前缀和数组一旦建好，整个数组就全出来了。

4.2 另一种更稳的写法：DFS 差值图

公式法虽然短，但对于新手来说，其实不太好讲清楚“为什么只用了这几个区间”。如果你想要一个更通用、更不容易出错的写法，可以直接按差值图去 DFS。

思路是：把输入的所有区间和都建到邻接表里，然后对每个未访问的节点设初值 0，再沿着边去推算邻居的 pre 值。

#include <bits/stdc++.h> using namespace std; using ll = long long; struct Edge { int to; ll w; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<vector<Edge>> g(n + 1); for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { ll val; cin >> val; int u = i - 1; // pre[i-1] int v = j; // pre[j] // pre[v] - pre[u] = val g[u].push_back({v, val}); g[v].push_back({u, -val}); } } vector<ll> pre(n + 1, LLONG_MAX); vector<int> vis(n + 1, 0); function<void(int)> dfs = [&](int u) { vis[u] = 1; for (auto &e : g[u]) { int v = e.to; if (!vis[v]) { pre[v] = pre[u] + e.w; dfs(v); } } }; for (int i = 0; i <= n; i++) { if (!vis[i]) { pre[i] = 0; dfs(i); } } for (int i = 1; i <= n; i++) { cout << pre[i] - pre[i - 1] << " \n"[i == n]; } return 0; }

这个写法堪称“万能钥匙”。它不需要任何关于 n 大小的特判，也不依赖具体公式。每个连通块只要有一个点被赋了 0，其他点就能通过差值关系全部推算出来。

它的思想也很符合直觉：差分图建好之后，DFS 就是在给整张图“定坐标”。每次从一个点走到另一个点，读数就加上边权。如果走到已经访问过的点，按理说不会产生矛盾，因为题目保证数据合法。

4.3 复杂度分析

两种写法的复杂度都是 O(n²)。

输入本身就有 n(n-1)/2 个区间和，所以读入是 O(n²)，这是无法避免的。公式法在读完输入之后只用了 O(n) 时间做推导；DFS 法在建图之后还要遍历所有边，也是 O(n²)，但和输入规模是同一个量级。

空间上，公式法用二维数组存输入，也是 O(n²)。DFS 法如果用邻接表，边的数量也是 O(n²)。在 n 只有几百的量级下，完全不用担心。

要强调的一点是，这题不存在比 O(n²) 更快的解法，因为你必须把每个输入值都读一遍，这是输入格式决定的。所以别去想着能不能优化到 O(n log n)，不现实。

5. 调试实录：这些坑我一开始全踩过

5.1 坑 1：眼睛盯着“区间和”，手却去读对角线

我第一次做类似题的时候，条件反射就是默认输入里包含 b[i][i] 这种单点区间值。结果下意识地在读入时用for j = i; j <= n，把对角线也当输入读进来了。这样会导致读入错位，后面所有数据全乱。

破解方式只有一个：看清题目。这题说的是长度至少为 2 的子段和，所以对角线根本不存在。你的读入循环必须是j = i + 1而不是j = i。

这个坑非常隐蔽，因为很多区间题的输入模板是 i 到 j，包括对角线。做题前把输入格式画一遍，比盯着屏幕发愣有效得多。

5.2 坑 2：n=2 还硬套公式

如果你用的是公式法，n=2 的时候会有sum[2][3]这个下标。可 n=2 根本不存在区间 [2,3]，数组越界会直接导致运行时错误。

即使没有越界，你的 pre1 也会被算成一个莫名其妙的值。我在本地测试时，就因为没判断 n 和 2 的大小，输出过 [0, 7] 以外的奇怪答案。

正确的思维是：n=2 时只有一个等式 a1+a2=sum(1,2)，这是一个欠定系统，随便令 a1=0 即可。你不能指望公式像 n≥3 时那样给出唯一结果，因为本来就不唯一。

5.3 坑 3：int 爆了却不自知

区间和可以非常大，尤其是当 a 数组的元素允许正负交替、绝对值很大的时候。如果你用 int 存 pre 或者 sum，中间减法很容易爆掉。

我个人的习惯是，看到题目里没有明确说“值域很小”，就一律用 long long。USACO 的这类题，区间和的范围往往能到 1e18 量级，int 只有 2e9 出头，根本不够用。

这不算什么技术难点，但爆 int 带来的 bug 最讨厌，因为有时候小数据看起来是对的，大数据一测全乱。提前用 long long 是最便宜的保险。

5.4 自己造数据：从答案倒推

如果你还是不确定自己的代码对不对，教你一个我常用的调试方法：自己当出题人。

随机生成一个数组 a，然后暴力算出所有长度至少为 2 的区间和，把这些区间和作为输入喂给你的程序。最后再把你程序输出的数组暴力求一遍区间和，两边的结果完全一致，才算通过。

这个方法能帮你发现几乎所有问题。它最大的好处是把“验证结果”这一步从手工脑算变成了程序自动化。你可以随机生成几百组数据，反复跑，比在评测系统里一次次提交等结果快得多。

6. 从这道题看一类“差分重建”题的通法

6.1 套路识别清单

Range Reconstruction 不是一道孤题。它属于很典型的一类题：给你一系列“差值信息”，让你还原一个数组或序列。

识别这类题有几个信号：

第一，输入里全是“区间和”“两点距离”“相邻差”“相对大小”这类信息。第二，题目没有给你直接的单点值，而是给你一堆两点之间的关系。第三，题意强调“输出任意一个合法答案”，而不是“输出唯一答案”。

一旦看到这些信号，你的第一反应应该是：引入前缀和、差分数组、或者某种“点到点”的差值图模型。这比直接列方程组要直观得多。

6.2 自由变量与字典序最小

这类题往往不会只考构造。它还可能给你加一个约束，比如要求构造出的数组字典序最小，或者所有元素都大于等于 0。

这时候差值图的优势就体现出来了。因为每个连通块内部节点的相对位置已经固定，你要做的事情就变成了：对这个连通块做整体平移，找到满足附加条件的那个偏移量。

如果要求所有元素非负，那么你只需要扫描一次 pre 数组，找到最小的 pre[i] - pre[i-1]，把整个连通块往上抬，直到每一项都非负。如果要求字典序最小，那就从前面开始贪心调整自由变量。

这部分内容在很多变形题里都会出现，提前练熟不吃亏。

6.3 用图模型还能判断数据是否矛盾

差值图还有一个隐藏用途：判断输入数据是否自洽。

如果在 DFS 过程中，你从一条路径算出了 pre[v] = x，但从另一条路径又算出了 pre[v] = y，而 x ≠ y，那么说明输入本身就矛盾了。

这个判断思路可以迁移到很多题目里，比如“给一堆区间和，判断是否存在一个数组满足所有条件”。做法就是建图，跑一遍 DFS，遇到冲突直接输出不存在。USACO 的这道题因为保证至少有一个合法数组，所以没有让你做这一步，但你要知道这个模型还能干这件事。

6.4 我的做题习惯：先固定一个点，再处理缺口

做这类题，我最后沉淀下来的习惯只有一句话：先人为固定一个坐标，再寻找所有能确定的点；剩下还没确定的点，就是从某个已确定点“绕路”能推出来的点。

这个习惯在处理 Range Reconstruction 时体现得非常明显：固定 pre0 = 0，一下子得到 pre2 到 pren；剩下的 pre1，通过 pre3 绕一条路得到。整个过程没有任何玄学，就是一步步填充差值图里还没填的点。

当你面对更复杂的构造题，比如只知道部分区间和、甚至区间和带权值限制时，这个“固定一个点 → 绕路推导 → 检查全局一致”的流程依然通用。它比死记公式要稳健得多。

个人经验是，这道题你至少应该亲手写两遍。第一遍用公式法，感受前缀和带来的简洁；第二遍用差值图 DFS，理解背后的图模型。写完之后，你再看任何“区间信息还原数组”的题，都不会觉得慌了。