前缀和与差分数组详解

如果你的解法在数组题上超时，修复的关键往往不是更花哨的数据结构，而是一个简单的思路：预处理一次，然后瞬间作答。

为此最可靠的两件工具，就是前缀和及其镜像——差分数组。两者结合，能让你回答区间求和问题、应用区间更新，速度远超朴素做法。它们是竞赛编程中的前缀和练习的基础主题，在 BIAA 我们很早就讲授它们，因为它们能解锁大量题目，同时为日后学习更重的数据结构建立直觉。

前缀和到底是什么

给定一个数组 arr，前缀和数组 P 存储的是累计总和：P[i] 等于 arr[0] + arr[1] + ... + arr[i]。你只需从左到右扫描一遍即可构建，因此构建耗费 O(n) 时间。

回报在于查询。从下标 l 到 r 的任意连续区间之和，就是：

sum(l, r) = P[r] - P[l - 1]

这是一次常数时间、O(1) 的查找。你不必为每个问题重新累加元素，只需做一次预处理，然后瞬间回答每次查询。如果一道题询问 q 次区间求和，你的总工作量就从大约 O(n 乘以 q) 降到 O(n + q)。

前缀和出现的场景

• 在固定数组上进行区间求和查询。
• 计数与频率问题，包括利用余数统计其和具有某种性质的子数组。
• 二维前缀和，将同样的思路扩展到网格，从而能在常数时间内对任意矩形求和。
• 当更新进入视野后，它是迈向线段树和树状数组（BIT）的垫脚石。

差分数组：逆向的前缀和

差分数组是前缀和的逆运算。前缀和把数组变成累计总和，而差分数组 D 存储的是差值：D[i] = arr[i] - arr[i - 1]。对 D 取前缀和即可重建原数组。

正是这种逆向关系让区间更新变得廉价。假设你必须给区间 [l, r] 中的每个元素加上一个值 v。朴素做法是每次更新 O(n)。而用差分数组，你只需触碰两个位置：

1. 在下标 l 处加上 v。
2. 在下标 r + 1 处减去 v。

现在每次更新都是 O(1)。记录完所有更新后，你对 D 跑一次前缀和即可恢复最终数组。处理 Q 次更新加上最后一遍扫描，是 O(Q + n)。

为何这些技能对竞赛至关重要

在像 USACO 这样的平台上，前缀和与差分数组是 Silver 组别的核心内容。竞赛评测机施加严格的时间限制，因此一个逻辑正确却为 O(n 乘以 q) 的循环仍可能失败，而 O(n + q) 的版本则能从容通过。识别出一道题何时可归结为「多次区间求和」或「多次区间加」，正是评测者所奖赏的技能。

官方 USACO 分为 Bronze、Silver、Gold 和 Platinum 四个组别。参赛资格、比赛时间窗口和晋级门槛各不相同，因此请务必在竞赛中心和 USACO 官方网站确认最新细节，而不要依赖逐年变动的数字。

行之有效的练习计划

• 从零实现一维前缀和，然后用暴力循环校验 sum(l, r)。
• 用差分数组解决一道经典的「给区间加值」问题，并确认重建后的数组。
• 把这两种思路扩展到二维网格。
• 对比运行时间，让提速变得具体可感，而非只停留在理论上。

这些技巧是我们构建竞赛编程项目的核心：学生先学会模式，在小规模输入上验证，再在竞赛压力下加以运用。如果你的孩子正在备战 USACO，或希望打下更扎实的算法基础，欢迎了解 BIAA 的竞赛编程方向，在有指导的练习与反馈中开始构建这些技能。