前缀和与差分 —— 从概念到公式

一、为什么需要前缀和？

先想一个场景：你有一个长度为 n 的数组，现在要反复问你「第 3 个数到第 7 个数的和是多少」。

最直接的做法：每次从 3 加到 7。如果数组很大（比如 10 万个数），问你 10 万次，那总共要算 100 亿次加法——太慢了。
如果换一种思路，我能不能提前把「前 i 个数的和」全部算好存起来，这样每次询问直接用减法得到结果？

这就是前缀和的核心思想——预处理，换时间。

---

二、一维前缀和

2.1 定义

对于原数组 a[1] ~ a[n]，定义前缀和数组 s：

s[i] = a[1] + a[2] + ... + a[i]   （前 i 个数的总和）

2.2 核心公式

s[i] = s[i-1] + a[i]

边界条件：s[0] = 0（前 0 个数的和为 0）。

公式的意思是：前 i 个数的和 = 前 i-1 个数的和 + 第 i 个数。

2.3 图示

假设原数组 a 如下：

下标：  1    2    3    4    5
a[]：  2    5    3    1    4

逐个计算前缀和：

s[1] = 0 + 2 = 2
s[2] = 2 + 5 = 7
s[3] = 7 + 3 = 10
s[4] = 10 + 1 = 11
s[5] = 11 + 4 = 15

得到前缀和数组 s：

s[]：  2    7    10   11   15
      ↑    ↑    ↑    ↑    ↑
      前1  前2  前3  前4  前5

可以直观地看到：s[i] 就是从第一个数一直加到第 i 个数的「累计值」。

2.4 用途：快速求区间和

现在想求 a[2] + a[3] + a[4]（即区间 [2, 4] 的和）：

区间[2,4]的和 = s[4] - s[1] = 11 - 2 = 9
验证：5 + 3 + 1 = 9  ✅

核心公式：

区间 [l, r] 的和 = s[r] - s[l-1]

文字理解：前 r 个数的和 减去 前 l-1 个数的和，剩下的就是第 l 个到第 r 个。

                   ┌─────────── 区间[l, r] ───────────┐
                   │                                   │
a[1] a[2] ... a[l-1]  a[l] a[l+1] ... a[r-1] a[r]  a[r+1] ...
├──── 前 l-1 项 ────┤├────────── 前 r 项 ──────────┤
                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                     s[r] = 前 r 项的总和
     s[l-1] = 前 l-1 项的总和
             
     区间和 = s[r] - s[l-1]

预处理完 s 数组后，每次求区间和只需要 O(1) 的时间（一次减法），这就是前缀和的威力。

---

三、二维前缀和

3.1 问题升级

如果你面对的不是一维数组，而是一个二维矩阵，想快速求出任意一个子矩形内所有数的和，怎么办？

    列1  列2  列3  列4
行1   1    2    3    4
行2   5    6    7    8
行3   9   10   11   12

比如：求从 [2][2] 到 [3][4] 这个 2×3 矩形里所有数的和。

类比一维的思路：二维前缀和就是提前算好从 [1][1] 到 [i][j] 这个矩形内所有数的总和。

3.2 核心公式

定义 s[i][j] = 从左上角 (1,1) 到右下角 (i,j) 的矩形区域内所有元素的和。

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

3.3 图解：容斥原理

公式看着复杂，其实核心就是容斥原理——两个有重叠的区域合并时，加完两边，减掉重叠。

             列1     列2    ...   列j-1    列j    列j+1
     ┌──────────────────────────────────────────────────┐
行1   │                                                  │
     │                      A区域                        │
 ...  │                  s[i-1][j]                       │
     │              ┌──────────────┐                     │
行i-1 │              │  重叠部分    │                     │
     │              │ s[i-1][j-1]  │                     │
     │              └──────────────┘                     │
     ├─────────────────────────────┬────────────────────┤
行i   │          B区域             │      a[i][j]       │
     │       s[i][j-1]            │      (当前格子)     │
     └─────────────────────────────┴────────────────────┘

把 s[i][j] 拆成三块来看：

• A 区域 = s[i-1][j]：第 1i-1 行、第 1j 列（不含第 i 行）
• B 区域 = s[i][j-1]：第 1i 行、第 1j-1 列（不含第 j 列）
• 重叠部分 = s[i-1][j-1]：A 和 B 都覆盖的左上角

根据容斥原理（两个集合的并集 = 各自之和 − 交集）：

s[i][j] = |A ∪ B| + a[i][j]
        = |A| + |B| − |A ∩ B| + a[i][j]
        = s[i-1][j] + s[i][j-1] − s[i-1][j-1] + a[i][j]

3.4 用途：求子矩阵和

现在想求矩形区域 (x1, y1) 到 (x2, y2) 的和：

子矩阵和 = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]

同样还是面积加减法：

(x1,y1) ───────────── (x1,y2)
   │                     │
   │    ┌────────────┐   │
   │    │  目标矩形    │   │
   │    │ (红色区域)   │   │
   │    └────────────┘   │
(x2,y1) ───────────── (x2,y2)

怎么从 s[x2][y2]（整个大矩形）扣出目标红色区域？

1. 减掉上边部分 s[x1-1][y2]
2. 减掉左边部分 s[x2][y1-1]
3. 左上角区域 s[x1-1][y1-1] 被减了两次，加回来

---

四、差分

4.1 差分是前缀和的逆运算

先回顾前缀和的定义：s[i] = a[1] + ... + a[i]。

那反过来，已知 s 怎么求 a？

a[i] = s[i] - s[i-1]

这就是差分。 对前缀和数组求差分，就得到原数组；对差分数组求前缀和，也得到原数组——两者互逆。

原数组 a
  │  求前缀和
  ▼
前缀和数组 s
  │  求差分（相邻两项相减）
  ▼
原数组 a

那差分有什么用？看一个场景：

如果要反复给数组的某个区间统一加上一个数，最后再看结果，能不能快速做？

暴力做法是每次从 l 到 r 逐个加，太慢。差分能做到时间复杂度是O(1)， 一次标记，最后统一还原。

---

五、一维差分

5.1 定义

对于原数组 a[1] ~ a[n]，差分数组 b：

b[i] = a[i] - a[i-1]

其中 b[1] = a[1]（a[0] = 0）。

5.2 核心操作：区间加 c

给 a[l] ~ a[r] 每个数都加 c，分成两步：

① 在差分数组上改两个位置 → ② 再对差分数组求一次前缀和，就得到修改后的原数组

改哪两个位置？

b[l]   += c
b[r+1] -= c

也就是说，在差分数组上做完标记后，只要再求一遍前缀和就能得到修改后的数组。
不是说好了差分和前缀和是逆运算吗？为什么这样改两个位置就能让一整段加上 c？
拿一个具体的例子走一遍就明白了。

---

举个具体的例子

假设原数组 a 长度为 6：

下标：     1    2    3    4    5    6
a[]：      2    5    3    1    4    6

先按定义造出差分数组 b（b[i] = a[i] - a[i-1]）：

b[1] = a[1] - 0      = 2
b[2] = a[2] - a[1]   = 5 - 2   = 3
b[3] = a[3] - a[2]   = 3 - 5   = -2
b[4] = a[4] - a[3]   = 1 - 3   = -2
b[5] = a[5] - a[4]   = 4 - 1   = 3
b[6] = a[6] - a[5]   = 6 - 4   = 2

b[]：      2    3   -2   -2    3    2

---

现在，我想给 a[3] ~ a[5] 每个数都加上 5

按照公式，改 b 的两个位置：

b[3] += 5      （原来是 -2，变成 3）
b[6] -= 5      （原来是 2，变成 -3）

修改后的 b：

下标：     1    2    3    4    5    6
b[]：      2    3    3   -2    3   -3
                    ↑ b[3] 从 -2 变成 3
                                   ↑ b[6] 从 2 变成 -3

---

关键一步：对修改后的 b 求前缀和，看看会发生什么

还记得前缀和怎么算吗？**s[i] = s[i-1] + b[i]**。一步步来：

s[1] = 0 + b[1] = 0 + 2  = 2
s[2] = 2 + b[2] = 2 + 3  = 5
s[3] = 5 + b[3] = 5 + 3  = 8    ← 注意，这里用的是修改后的 b[3]（加了 5）
s[4] = 8 + b[4] = 8 + (-2)= 6
s[5] = 6 + b[5] = 6 + 3  = 9
s[6] = 9 + b[6] = 9 + (-3)= 6    ← 这里用的是修改后的 b[6]（减了 5）

得到新的 s：

s[]：      2    5    8    6    9    6

对比原来的 a：

原来 a：   2    5    3    1    4    6
新的 s：   2    5    8    6    9    6
                          ↑    ↑    ↑
                     a[3]+5  a[4]+5  a[5]+5

正好只有 a[3] ~ a[5] 加了 5，前面和后面都没变！–很神奇对吧！

---

为什么？

原因藏在前缀和的累加特性里。把 b 看成一系列”标记“：

b[]：  2    3    3   -2    3   -3
                 ↑
           这里 b[3] 多了一个 +5
                                ↑
                          这里 b[6] 多了一个 -5

对 b 求前缀和时，每个位置的值会一直往后累加：

位置1：       2                                 = 2
位置2：       2 + 3                             = 5
位置3：       2 + 3 + 3      ← +5 从这里开始     = 8 ← 比原来多了 5
位置4：       2 + 3 + 3 + (-2)    ← +5 还在继续   = 6 ← 比原来多了 5
位置5：       2 + 3 + 3 + (-2) + 3               = 9 ← 比原来多了 5
位置6：       2 + 3 + 3 + (-2) + 3 + (-3)        = 6 ← +5 和 -5 抵消了！
           ↑ 前 5 项还带着 +5     这里又减了 5 ──┘

把过程画出来看更清楚：

在 b[3] 放一个 +5 → 从位置 3 开始，所有数都多了 5
                                              ┌───────────────────
位置:    1      2      3      4      5      6 │
累加:    2      5      8      6      9      6 │
        ──────────────────────────────────────┘
                            ← +5 一直跟着 →  
                                              然后在 b[6] 放一个 -5 → +5 被抵消

位置:    1      2      3      4      5      6
累加:    2      5      8      6      9      6  
                                     +5 被 -5 抵消 → 变回原样

结论： b[l] += c 让 +c 从位置 l 开始一直往后传，b[r+1] -= c 让它在 r+1 处被抵消。一传一挡，c 就只落在了 [l, r] 这一段上。

5.3 完整流程

1. 由原数组 a 构造差分数组 b
2. 在 b 上进行区间修改（b[l] += c, b[r+1] -= c）
3. 所有修改完成后，对 b 求一遍前缀和 → 得到修改后的 a

前缀和和差分正好互补：

• 前缀和：一次预处理，多次查询区间和
• 差分：多次修改区间值，最后一次性看结果

---

六、二维差分

6.1 定义

和一维完全对称：对 b 求二维前缀和 = 原矩阵 a。

构造公式（对二维前缀和公式做逆运算）：

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

6.2 核心操作：子矩阵加 c

给矩形 (x1,y1) 到 (x2,y2) 内每个数加 c，只需改四个点：

b[x1][y1]     += c
b[x1][y2+1]   -= c
b[x2+1][y1]   -= c
b[x2+1][y2+1] += c

6.3 图解

一维是在两端做标记，二维是在四个角做标记：

b[x1][y1] += c        b[x1][y2+1] -= c
     ● ──────────────────────── ●
     │                          │
     │       目标区域            │
     │      (+c 的区域)          │
     │                          │
     ● ──────────────────────── ●
b[x2+1][y1] -= c      b[x2+1][y2+1] += c

和一维同理，四个标记经过二维前缀和后，只有矩形内部被加了 c。

6.4 完整流程

1. 构造二维差分数组 b
2. 在 b 上进行子矩阵修改（改四个角）
3. 所有修改完成后，对 b 求二维前缀和 → 得到修改后的矩阵 a

---

七、总结对照

公式速查表

场景	公式	用途
一维前缀和	s[i] = s[i-1] + a[i]	预处理
一维区间和	sum[l,r] = s[r] - s[l-1]	快速查询
二维前缀和	s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]	预处理
二维子矩阵和	sum = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]	快速查询
一维差分	b[l] += c, b[r+1] -= c	区间加减
二维差分	b[x1][y1] += c, b[x1][y2+1] -= c, b[x2+1][y1] -= c, b[x2+1][y2+1] += c	子矩阵加减

一张图理解全部关系

         求前缀和               求差分
原数组 ────────→ 前缀和数组 ────────→ 原数组

         求差分                 求前缀和
原数组 ────────→ 差分数组 ────────→ 原数组

前缀和与差分就像积分与求导，是互逆的运算

使用场景

算法	什么时候用	耗时
前缀和	多次查询区间和/子矩阵和	预处理 O(n)，每次查询 O(1)
差分	多次修改区间/子矩阵的值，最后一次性查看结果	每次修改 O(1)，最后恢复 O(n)
前缀和 + 差分	多次修改 + 多次查询	差分做修改，前缀和做查询，中间通过「求前缀和」衔接

关键注意点

1. 数组下标从 1 开始，避免出现 l-1 = 0 时越界
2. 设 s[0] = 0（一维）或 s[0][*] = s[*][0] = 0（二维），统一边界条件
3. 先修改，后查询——差分所有的修改操作做完后，最后求一遍前缀和才能得到最终结果
4. 二维的「面积加减法」理解了，前缀和和差分的四个公式其实是一个思路，不需要死记硬背

---

前缀和是「累加」，差分是「标记」——这对互逆的算法体现了预处理和批量操作的核心思想，是算法竞赛和面试中最高频的基础技巧之一。