区间类结构基础：前缀和与差分

学到这里，很多数据结构都在围绕“单点操作”展开：查一个值、插一个点、删一个节点、维护一个最值。但在很多实际问题里，我们关心的并不是单个位置，而是一整段区间。例如：

某个区间的元素和是多少；
某一段范围需要统一加一个值；
多次区间更新后，最终每个位置的值是什么；
二维网格中某个子矩形的总和是多少。

这类问题一旦用最直观的暴力去做，通常很容易超时。于是数据结构里就发展出一类非常经典的基础工具：前缀和与差分。它们看起来简单，甚至不像“树”或“图”那样有复杂结构，但在区间问题里威力非常大。很多更高级的结构，例如树状数组和线段树，其实也可以看成是在它们思想上的进一步增强。

一、为什么区间问题不能总靠暴力

假设有一个数组，长度为 n。如果你要频繁回答：

区间 [l, r] 的和是多少？

最直观的做法当然是每次从 l 加到 r，复杂度通常是 O(n)。如果查询很多次，总成本会非常高。

再比如：

每次要把区间 [l, r] 所有元素都加上某个值。

如果每次都真的一个个加，也会非常慢。

所以这类问题的关键不在于“能不能做”，而在于：

能不能把一次对整段区间的工作，提前转化成更便宜的预处理或更紧凑的增量表示。

二、什么是前缀和

前缀和可以先理解成：

预先把从开头到每个位置的累计和都算出来。

例如有数组 a，构造一个数组 sum，其中：

1	sum[i] = a[1] + a[2] + ... + a[i]

这样一来，区间 [l, r] 的和就不需要重新遍历整段，而可以通过：

1	sum[r] - sum[l - 1]

直接得到。

这就是前缀和的本质：

用一次预处理；
换取后续查询极快。

三、前缀和为什么能把区间求和变成 O(1)

因为区间和本来就是“前一段累计减去更前面一段累计”。

例如：

sum[r] 包含了从开头到 r 的所有元素；
sum[l - 1] 包含了从开头到 l - 1 的所有元素；
两者一减，刚好只剩下 [l, r] 这一段。

于是：

预处理一次前缀和通常是 O(n)；
之后每次区间求和查询通常是 O(1)。

这是一种非常经典的“预处理换查询速度”思路。

四、前缀和适合什么场景

前缀和最适合：

原数组基本不变；
查询很多；
问题以区间和、区间计数、区间统计为主。

典型场景包括：

统计一段时间内的访问量；
快速求子数组和；
二维矩阵中求子矩形和；
许多动态规划和滑动窗口的预处理。

它的核心优势是查询快，但前提是：

数据不应该频繁修改。

五、前缀和的局限在哪里

如果数组经常更新，比如：

某个位置值变了；
或很多位置要反复修改；

那么整个前缀和数组可能都要重新维护，代价就会比较高。

这说明前缀和更擅长：

静态数据；
多次查询；
少修改。

而一旦更新操作很多，就可能需要更强的数据结构，例如后面的树状数组和线段树。

六、什么是差分数组

如果说前缀和是“为了快查区间结果”，那差分可以理解成：

为了快做区间修改，而把变化量集中记录在边界上。

对于数组 a，可以构造差分数组 diff：

1	diff[i] = a[i] - a[i - 1]

从这个定义可以看出：

差分记录的是相邻位置之间的变化；
原数组可以通过对差分做前缀和恢复出来。

也就是说：

前缀和是“由原数组得到累计结果”；
差分则是“把原数组改写成变化量表示”。

七、差分为什么适合区间加法更新

假设要对区间 [l, r] 都加上一个值 x。

如果直接改原数组，需要把区间内每个元素都加一次；但在差分数组里，只需要做两件事：

diff[l] += x
diff[r + 1] -= x

为什么这样就够了？因为：

从 l 开始，前缀和恢复时整体会多出 x；
到了 r + 1 再减掉，影响就停止了；
最终 [l, r] 整段都会被统一加上 x。

所以差分最经典的价值就是：

把整段区间的批量修改，压缩成两个边界点操作。

八、差分和前缀和是什么关系

它们可以看成互逆关系：

前缀和：从原数组得到累计数组；
差分：从原数组得到变化数组；
原数组可以通过差分前缀和恢复；
区间和可以通过前缀和快速计算。

从更抽象的角度讲：

前缀和擅长“从点到段”的查询压缩；
差分擅长“从段到点”的修改压缩。

这个对偶关系非常值得真正理解。

九、二维前缀和和二维差分怎么理解

这套思想并不只适用于一维数组，也可以推广到二维矩阵。

1. 二维前缀和

预处理从左上角到某个位置的子矩形累计和，于是任意子矩形求和就能通过几个角点组合得到。

2. 二维差分

对一个子矩形整体加值时，可以只在若干边界角点做标记，最后再还原整张矩阵。

这在很多网格类问题里非常常见，例如：

地图叠加；
图像区域更新；
矩阵多次批量加减；
热力图统计。

十、前缀和与差分的共同本质是什么

它们表面看是两个不同技巧，但本质上非常统一：

通过改变数据表示方式，把重复的大量操作压缩成更少量的运算。

这也是数据结构里很核心的一种思维方式：

不一定每次都直接在原问题上操作；
可以先换一种表示，再让问题变简单。

前缀和与差分的意义，远远不止几道数组题，而是在训练这种“表示转换”的能力。

十一、学习这部分时最容易踩的坑

1. 分不清前缀和适合查、差分适合改

这是最常见的混淆点。

2. 只会公式，不理解边界为什么这么处理

如果不理解“累计”和“变化量”的本质，就很容易写错下标。

3. 不会把一维思路推广到二维

其实二维只是多一层包含关系，本质思路一样。

4. 把前缀和用在频繁更新场景

这时候就容易意识到它的不足，需要更动态的数据结构。

总结

前缀和与差分的重要性，不只是因为它们简单，而是因为它们非常纯粹地体现了“通过改变表示方式降低复杂度”的思想。真正值得先建立起来的，是这些核心认识：

前缀和适合静态区间查询，把区间和压缩成常数时间计算；
差分适合批量区间更新，把整段修改压缩成边界变化；
二者可以看成一对互补结构：一个擅长查，一个擅长改；
这类结构的本质不是多复杂，而是通过预处理和表示转换减少重复劳动；
它们的思想可以自然推广到二维甚至更高维；
真正学会前缀和与差分，不是会套公式，而是能看出问题是否适合“把区间工作变成边界工作”。

把这一篇理解透之后，后面再去学树状数组和线段树时，你会更容易明白：那些看起来更高级的结构，其实就是在“动态维护前缀和 / 区间信息”这条路上继续往前走。

参考资源：