把一万次区间求和压成一次预处理：前缀和与差分的互逆

前缀和是把数组从头累加到每个位置的预计算结果，区间和于是变成两个前缀值相减；差分数组是它的逆运算，把一段区间统一加减压缩成两个端点上的修改，最后再求前缀和还原。两者共用同一个恒等式，只是方向相反，因此一个擅长多次查询，一个擅长多次更新。最常见的误区是把前缀和用在频繁修改的数组上，或以为差分数组能 O(1) 查询单点，以及忘记 0-indexed 与 1-indexed 的下标换算。读完你能根据“查得多还是改得多”选对结构，写对二维容斥公式，并知道什么时候该换树状数组或线段树。

title: 把一万次区间求和压成一次预处理：前缀和与差分的互逆 date: 2026-11-06T10:00:00+08:00 type: kb tags: [科普] status: published summary: 前缀和是把数组从头累加到每个位置的预计算结果，区间和于是变成两个前缀值相减；差分数组是它的逆运算，把一段区间统一加减压缩成两个端点上的修改，最后再求前缀和还原。两者共用同一个恒等式，只是方向相反，因此一个擅长多次查询，一个擅长多次更新。最常见的误区是把前缀和用在频繁修改的数组上，或以为差分数组能 O(1) 查询单点，以及忘记 0-indexed 与 1-indexed 的下标换算。读完你能根据“查得多还是改得多”选对结构，写对二维容斥公式，并知道什么时候该换树状数组或线段树。 ---

是什么

前缀和（prefix sum）是把数组从开头到每个位置的累计值预先算出来，存成一条“运行中的总额”。有了它，任意区间 [l, r] 的和不必逐项相加，只要两个前缀值相减。差分数组（difference array）是它的逆运算：只存相邻元素的差，对原数组一段区间统一加 v，就变成在差分数组的两个端点上各改一次；最后对差分数组求一遍前缀和，所有修改一次性还原。

一句话直觉：前缀和把“一段区间”折叠成“两个端点的差”，差分把“一段区间的修改”折叠成“两个端点的加减”。它们是同一个恒等式的两个方向——对前缀和数组再取差分回到原数组，对差分数组取前缀和也回到原数组。

典型场景包括：静态数组上的大量区间求和（一周气温的区间均值、股价区间涨跌、游戏里的伤害统计）、二维矩阵的子矩形求和（图像处理中的积分图）、区间批量加减后只关心最终结果（会议室占用、航班订座、区间覆盖计数），以及“子数组和等于 k”这类前缀和配哈希表的题。

核心原理

先看一维。定义 pre[0] = 0，pre[i] = a[0] + … + a[i-1]，数组长度为 n+1。那么区间和可以写成：

sum(l, r) = pre[r+1] - pre[l]

原因是 pre[r+1] 覆盖前 r+1 个元素，pre[l] 覆盖前 l 个，两者相减，[0, l) 的部分正好抵消，只剩 [l, r]。可以把 pre 想成账本每页页脚的“累计支出”：要知道第 3 天到第 7 天花掉多少，不必翻七页流水，拿第 7 天页脚减去第 2 天页脚即可。pre[0]=0 这一格代表“第 0 天之前”，专门用来消掉 l=0 的特判；省掉它，代码里就迟早出现一个 if (l == 0)。

from itertools import accumulate

def build_prefix(a):
    return [0, *accumulate(a)]        # pre[i] = a[0] + ... + a[i-1]

def range_sum(pre, l, r):             # 闭区间 [l, r]
    return pre[r + 1] - pre[l]

def apply_range_adds(a, ops):         # 多次区间加，一次性还原
    n = len(a)
    diff = [0] * (n + 1)
    for l, r, v in ops:
        diff[l] += v
        diff[r + 1] -= v
    cur = 0
    for i in range(n):
        cur += diff[i]
        a[i] += cur
    return a

复杂度账很清楚：预处理 O(n)，之后每次查询 O(1)，q 次查询总计 O(n+q)；朴素做法是 O(nq)。当 n 和 q 都是十万级，差距是十亿次加法与二十万次加法。

二维只是把同一件事做两遍。令 pre[i][j] 表示左上角 (0,0) 到 (i-1,j-1) 的矩形和，则：

pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i-1][j-1]

查询 (x1,y1) 到 (x2,y2) 的子矩形：

S = pre[x2+1][y2+1] - pre[x1][y2+1] - pre[x2+1][y1] + pre[x1][y1]

减去的两个大矩形在左上角重叠了一块，被减了两次，所以要加回一次。这就是容斥，和集合的 |A∪B| = |A| + |B| - |A∩B| 是同一个道理。

再看差分。定义 d[0] = a[0]，d[i] = a[i] - a[i-1]。对 [l, r] 整体加 v 时，只需：

d[l] += v; d[r+1] -= v

因为区间内部的相邻差没有变化，真正变的只有 l 处“比前一个元素高出的量”和 r+1 处“回落”的量。可以想成走一段台阶：在 l 处把地面整体抬高 v，在 r+1 处再把地面降回去，中间自然整段升高。最后从前往后累加 d，就得到修改后的数组。k 次更新的总代价是 O(n+k)，而不是 O(nk)。

二维差分是端点思想的四次版：要给子矩形统一加 v，只需在 d[x1][y1] += v、d[x2+1][y1] -= v、d[x1][y2+1] -= v、d[x2+1][y2+1] += v，再对 d 做一次二维前缀和。四个角一加三减，矩形外的区域正好被抵消，和二维前缀和的容斥完全对称。

差分和前缀和互为逆运算，这一点值得单独记住：对一个数组先差分再前缀和，会原样回到它；反过来先前缀和再差分，也会回到它，只是下标整体平移了一位。它是离散版本的“求导与积分”——差分是求导，前缀和是积分，二者差一个常数，而 pre[0]=0 或 d[0]=a[0] 正是在固定这个常数。也正因为如此，只有“可逆”的运算才能照搬这套做法：和、异或、非零数的积、计数都能靠相减或相消还原；最大值、最小值、gcd 没有逆元，区间查询就得换稀疏表或线段树。

同理还有前缀异或：px[i] = a[0] ^ … ^ a[i-1]，区间异或值等于 px[r+1] ^ px[l]。异或是自己的逆运算，所以这套结构不需要额外改造。

前缀和还能和哈希表组合。要数有多少子数组的和等于 k，从左往右累加，把每个前缀和的出现次数记进哈希表；扫到当前位置 cur 时，只要找 cur-k 出现过几次，就得到以当前位置结尾的合法子数组数。表里要先放 {0: 1}，代表“空前缀”，否则从下标 0 开始的子数组会被漏掉。这个做法对负数同样成立，而滑动窗口在负数面前会失效，这是两者的关键分界。

常见考点与误区

  • 以为前缀和能扛在线修改：面试官常问“数组元素会变，还能用前缀和吗”，很多人答“改完重算一遍”。实际上被改位置之后的 pre 全部失效，重建是 O(n)，改 q 次就退化成 O(nq)；正确做法是树状数组或线段树，把单点修改和区间查询都压到 O(log n)。
  • 以为差分数组能 O(1) 查询：差分的 O(1) 是“更新”，它并不维护每个点的当前值。要拿单点的值仍得从头累加，单次 O(n)；全部重建一次后可以 O(1) 查所有点，但更新与查询交替时就不划算。此时应当用树状数组维护差分数组，把单点查询降到 O(log n)。
  • 下标和边界写错：0-indexed 用 pre[r+1]-pre[l]，1-indexed 用 pre[r]-pre[l-1]；差分的 r+1 可能等于 n，数组要开 n+1，或者显式判越界。二维前缀数组要开 (n+1)×(m+1)，四个角的下标各不同，最容易漏掉 +1。
  • 以为子数组求和都能滑窗：数组含负数时，右指针右移不会让窗口和单调增大，滑窗的前提被破坏。面试里把“和为 k 的子数组”写成滑窗是典型失分点；前缀和加哈希表不依赖单调性，仍然有效。
  • 以为前缀和什么都能求：max、min、gcd 没有逆运算，pre[r]-pre[l] 这类减法不成立，区间最值要靠稀疏表或线段树；前缀积遇到 0 也要单独处理，否则“除回去”会出错。
  • 忽视溢出与浮点误差：十万个 1e9 相加会超出 32 位有符号整数的上限；浮点数用两个很大且相近的前缀相减，有效位会被吃掉。能整数化就整数化，求和一律用 64 位。

实践建议

  • 先判断数据是“静态”还是“动态”：只查不改用前缀和；只改、最后问结果用差分；边改边查用树状数组或线段树；区间加且区间求和，用双树状数组或带懒标记的线段树，不要硬套差分。
  • 坐标范围很大或很稀疏时，不要真的开 1e9 长度的数组。把修改写成 (位置, 增量) 事件，排序后扫描，或者离散化端点，这是航班订座、会议室占用这类题的标准做法。
  • 统一用 1-indexed、pre[0]=0 的风格，把区间查询封装成只接受闭区间的函数，把 +1 收在一处；写完用随机小数据和暴力法对拍，比肉眼检查有效得多。
  • 用 64 位整数存前缀和，并在读题时估算上界 n × max|a|；二维前缀注意 n×m 的内存，能原地复用就原地复用。
  • 子数组计数用“前缀值 → 出现次数”的哈希表，想复原下标时改存最早或最晚位置；别忘了空前缀，也别忘了在取模场景下把负余数归一。

参考资料：

  • USACO Guide: Introduction to Prefix Sums — https://usaco.guide/silver/prefix-sums
  • USACO Guide: More on Prefix Sums（二维前缀和与差分）— https://usaco.guide/silver/more-prefix-sums
  • Princeton Competitive Programming: Prefix Sums — https://competitive-programming.cs.princeton.edu/ps_s24
  • GeeksforGeeks: Prefix Sum Technique — https://www.geeksforgeeks.org/dsa/understanding-prefix-sums

一句话总结：前缀和把区间查询压成两次减法，差分把区间更新压成两次加法，二者互逆；选哪个，取决于你更怕查询还是更怕修改。

相关阅读

← 返回文章志