前缀和与差分：修订间差异

可视化wikitext

2025年5月12日 (一) 00:24的最新版本

模板:Note

概述[编辑 | 编辑源代码]

前缀和（Prefix Sum）与差分（Difference）是处理数组区间问题的两种互补技术，广泛应用于高效计算区间和、动态维护数组等场景。

前缀和：通过预处理构建新数组，其中每个元素存储原数组从起始位置到当前位置的累加和，使得区间和查询可在O(1)时间内完成。
差分：通过构建相邻元素的差值数组，支持对原数组的区间进行快速增减操作，最终通过差分数组还原修改后的原数组。

两者关系如下图所示：

前缀和[编辑 | 编辑源代码]

一维前缀和[编辑 | 编辑源代码]

给定数组 $A [0 . . n - 1]$ ，其前缀和数组 $S$ 定义为： $S [i] = {\begin{cases} 0 & i = - 1 \\ S [i - 1] + A [i] & i \geq 0 \end{cases}$

代码实现[编辑 | 编辑源代码]

def prefix_sum(arr):
    n = len(arr)
    s = [0] * (n + 1)
    for i in range(n):
        s[i + 1] = s[i] + arr[i]
    return s

# 示例
arr = [1, 3, 5, 2, 4]
s = prefix_sum(arr)
print(s)  # 输出: [0, 1, 4, 9, 11, 15]

# 查询区间[2,4]的和（左闭右闭）
print(s[4 + 1] - s[2])  # 输出: 11 (5+2+4)

二维前缀和[编辑 | 编辑源代码]

对于二维数组 $A [m] [n]$ ，其前缀和 $S [i] [j]$ 表示以(0,0)为左上角、(i,j)为右下角的矩形区域和： $S [i] [j] = S [i - 1] [j] + S [i] [j - 1] - S [i - 1] [j - 1] + A [i] [j]$

示例[编辑 | 编辑源代码]

差分[编辑 | 编辑源代码]

一维差分[编辑 | 编辑源代码]

给定数组 $A [0 . . n - 1]$ ，其差分数组 $D$ 满足： $D [i] = {\begin{cases} A [0] & i = 0 \\ A [i] - A [i - 1] & i > 0 \end{cases}$

区间修改[编辑 | 编辑源代码]

对原数组 $A [l . . r]$ 区间增加 $k$ ，只需： $D [l] + = k, D [r + 1] - = k$

代码示例[编辑 | 编辑源代码]

def difference_array(arr):
    n = len(arr)
    d = [0] * n
    d[0] = arr[0]
    for i in range(1, n):
        d[i] = arr[i] - arr[i - 1]
    return d

# 区间增减操作
def apply_diff(d, l, r, k):
    d[l] += k
    if r + 1 < len(d):
        d[r + 1] -= k

# 示例
arr = [1, 3, 5, 2, 4]
d = difference_array(arr)
apply_diff(d, 1, 3, 2)  # 对arr[1..3]加2

# 还原数组
for i in range(1, len(d)):
    d[i] += d[i - 1]
print(d)  # 输出: [1, 5, 7, 4, 4]

二维差分[编辑 | 编辑源代码]

类似一维情况，二维差分通过四个角点的操作实现矩形区域修改： $D [x 1] [y 1] + = k$
$D [x 2 + 1] [y 1] - = k$
$D [x 1] [y 2 + 1] - = k$
$D [x 2 + 1] [y 2 + 1] + = k$

应用案例[编辑 | 编辑源代码]

案例1：区间统计[编辑 | 编辑源代码]

问题：给定学生每日学习时长记录，快速回答任意时间段内的总学习时长。
解决方案：使用前缀和数组预处理。

案例2：航班预订统计[编辑 | 编辑源代码]

问题：有n个航班，每个预订记录包含 $[f i r s t, l a s t, s e a t s]$ ，求最终每个航班的座位数。
解决方案：使用差分数组处理区间增减，最后还原数组。

def corpFlightBookings(bookings, n):
    diff = [0] * (n + 2)
    for first, last, seats in bookings:
        diff[first] += seats
        diff[last + 1] -= seats
    for i in range(1, n + 1):
        diff[i] += diff[i - 1]
    return diff[1:n + 1]

# 输入: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
# 输出: [10,55,45,25,25]

复杂度分析[编辑 | 编辑源代码]

操作复杂度对比
操作	前缀和	差分
预处理	O(n)	O(n)
单点查询	O(1)	O(n)
区间查询	O(1)	不支持
区间修改	不支持	O(1)

进阶技巧[编辑 | 编辑源代码]

前缀和+哈希表：解决子数组和等于特定值的问题（如LeetCode 560题）
差分+离散化：处理大规模稀疏区间问题
多维推广：三维及更高维度的前缀和应用（如立体空间体积计算）

模板:Tip

参见[编辑 | 编辑源代码]

@@ 第1行： / 第1行： @@
-{{Note|本条目详细介绍算法设计中的'''前缀和与差分'''技术，适用于初学者及需要巩固该概念的程序员。内容包含基础原理、代码实现、实际应用及复杂度分析。}}
+{{Note|本条目将详细介绍算法中的'''前缀和'''与'''差分'''技术，包含基础概念、实现方法及实际应用案例。}}
 == 概述 ==
-'''前缀和（Prefix Sum）'''与'''差分（Difference Array）'''是两种互补的算法设计技巧，常用于高效处理'''区间查询'''和'''区间更新'''问题。前缀和通过预处理数组实现快速区间求和，而差分则通过标记变化实现高效区间修改。
+'''前缀和'''（Prefix Sum）与'''差分'''（Difference）是处理数组区间问题的两种互补技术，广泛应用于高效计算区间和、动态维护数组等场景。
-=== 核心思想 ===
+* '''前缀和'''：通过预处理构建新数组，其中每个元素存储原数组从起始位置到当前位置的累加和，使得区间和查询可在O(1)时间内完成。
-* '''前缀和'''：将原始数组转换为前<math>i</math>项和的数组，使得区间和查询可在<math>O(1)</math>时间内完成。
+* '''差分'''：通过构建相邻元素的差值数组，支持对原数组的区间进行快速增减操作，最终通过差分数组还原修改后的原数组。
-* '''差分'''：记录相邻元素的差值，通过累加差分数组还原原数组，使区间增减操作降为<math>O(1)</math>时间复杂度。
+两者关系如下图所示：
+<mermaid>
+graph LR
+    A[原数组] -->|预处理| B[前缀和数组]
+    A -->|相邻元素差值| C[差分数组]
+    B -->|逆运算| C
+    C -->|前缀和运算| A
+</mermaid>
 == 前缀和 ==
 === 一维前缀和 ===
 给定数组<math>A[0..n-1]</math>，其前缀和数组<math>S</math>定义为：
-<math>S[i] = \sum_{k=0}^{i} A[k] \quad \text{其中} \ S[-1]=0</math>
+<math>S[i] = \begin{cases}
+& i = -1 \\
+S[i-1] + A[i] & i \geq 0
+\end{cases}</math>
 ==== 代码实现 ====
@@ 第17行： / 第28行： @@
 def prefix_sum(arr):
      n = len(arr)
-     prefix = [0] * (n + 1)
+     s = [0] * (n + 1)
      for i in range(n):
-         prefix[i + 1] = prefix[i] + arr[i]
+         s[i + 1] = s[i] + arr[i]
-     return prefix
+     return s
 # 示例
-arr = [3, 1, 4, 1, 5]
+arr = [1, 3, 5, 2, 4]
-prefix = prefix_sum(arr)
+s = prefix_sum(arr)
-print(prefix)  # 输出: [0, 3, 4, 8, 9, 14]
+print(s)  # 输出: [0, 1, 4, 9, 11, 15]
+# 查询区间[2,4]的和（左闭右闭）
+print(s[4 + 1] - s[2])  # 输出: 11 (5+2+4)
 </syntaxhighlight>
-==== 区间查询 ===
-查询区间<math>[l, r]</math>的和：<math>S[r+1] - S[l]</math>（注意Python中数组从0开始索引）。
 === 二维前缀和 ===
-扩展至二维矩阵，定义<math>S[i][j]</math>为从<math>(0,0)</math>到<math>(i,j)</math>的子矩阵和：
+对于二维数组<math>A[m][n]</math>，其前缀和<math>S[i][j]</math>表示以(0,0)为左上角、(i,j)为右下角的矩形区域和：
 <math>S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j]</math>
+==== 示例 ====
+<mermaid>
+graph TD
+    A[[" " 1 3 5
+4 6
+8 9]] --> B[["0 0 0 0
+1 4 9
+3 9 17
+10 24 42"]]
+</mermaid>
 == 差分 ==
 === 一维差分 ===
-差分数组<math>D</math>满足：
+给定数组<math>A[0..n-1]</math>，其差分数组<math>D</math>满足：
-<math>D[i] = A[i] - A[i-1] \quad \text{（假设} \ A[-1]=0 \text{）}</math>
+<math>D[i] = \begin{cases}
+A[0] & i = 0 \\
+A[i] - A[i-1] & i > 0
+\end{cases}</math>
-==== 区间更新 ===
+==== 区间修改 ====
-对原数组<math>A[l..r]</math>增加<math>k</math>，只需：
+对原数组<math>A[l..r]</math>区间增加<math>k</math>，只需：
-* <math>D[l] += k</math>
+<math>D[l] += k,\ D[r+1] -= k</math>
-* <math>D[r+1] -= k</math>
 ==== 代码示例 ====
@@ 第49行： / 第73行： @@
 def difference_array(arr):
      n = len(arr)
-     diff = [0] * (n + 1)
+     d = [0] * n
-     diff[0] = arr[0]
+     d[0] = arr[0]
      for i in range(1, n):
-         diff[i] = arr[i] - arr[i - 1]
+         d[i] = arr[i] - arr[i - 1]
-     return diff
+     return d
-def apply_diff(diff, l, r, k):
+# 区间增减操作
-     diff[l] += k
+def apply_diff(d, l, r, k):
-     if r + 1 < len(diff):
+     d[l] += k
-         diff[r + 1] -= k
+     if r + 1 < len(d):
+         d[r + 1] -= k
 # 示例
-arr = [1, 2, 3, 4, 5]
+arr = [1, 3, 5, 2, 4]
-diff = difference_array(arr)
+d = difference_array(arr)
-apply_diff(diff, 1, 3, 2)  # 对arr[1..3]增加2
+apply_diff(d, 1, 3, 2)  # 对arr[1..3]加2
 # 还原数组
-for i in range(1, len(arr)):
+for i in range(1, len(d)):
-     diff[i] += diff[i - 1]
+     d[i] += d[i - 1]
-print(diff[:-1])  # 输出: [1, 4, 5, 6, 5]
+print(d)  # 输出: [1, 5, 7, 4, 4]
 </syntaxhighlight>
 === 二维差分 ===
-类似地，二维差分可通过四个角点操作实现矩形区域的增减。
+类似一维情况，二维差分通过四个角点的操作实现矩形区域修改：
+<math>D[x1][y1] += k</math><br>
+<math>D[x2+1][y1] -= k</math><br>
+<math>D[x1][y2+1] -= k</math><br>
+<math>D[x2+1][y2+1] += k</math>
 == 应用案例 ==
-=== 案例1：子数组和等于K ===
+=== 案例1：区间统计 ===
-'''问题'''：统计数组中连续子数组和为<math>K</math>的数量。<br>
+'''问题'''：给定学生每日学习时长记录，快速回答任意时间段内的总学习时长。<br>
-'''解法'''：利用前缀和+哈希表，时间复杂度<math>O(n)</math>。
+'''解决方案'''：使用前缀和数组预处理。
 === 案例2：航班预订统计 ===
-'''问题'''：处理<math>n</math>次航班预订，每次预订从<math>i</math>到<math>j</math>的<math>k</math>个座位，求最终每班次的座位数。<br>
+'''问题'''：有n个航班，每个预订记录包含<math>[first, last, seats]</math>，求最终每个航班的座位数。<br>
-'''解法'''：差分数组模拟预订操作后还原。
+'''解决方案'''：使用差分数组处理区间增减，最后还原数组。
-<mermaid>
+<syntaxhighlight lang="python">
-graph LR
+def corpFlightBookings(bookings, n):
-     A[原始数组] -->|预处理| B[前缀和数组]
+    diff = [0] * (n + 2)
-     B -->|O(1)查询| C[区间和]
+     for first, last, seats in bookings:
-     D[差分数组] -->|O(1)更新| E[区间增减]
+        diff[first] += seats
-    E -->|还原| A
+        diff[last + 1] -= seats
-</mermaid>
+     for i in range(1, n + 1):
+        diff[i] += diff[i - 1]
+     return diff[1:n + 1]
+# 输入: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
+# 输出: [10,55,45,25,25]
+</syntaxhighlight>
 == 复杂度分析 ==
 {| class="wikitable"
-|+ 时间复杂度对比
+|+ 操作复杂度对比
-! 操作 !! 原始数组 !! 前缀和/差分
+! 操作 !! 前缀和 !! 差分
+|-
+| 预处理 || O(n) || O(n)
+|-
+| 单点查询 || O(1) || O(n)
 |-
-| 区间查询 || <math>O(n)</math> || <math>O(1)</math>
+| 区间查询 || O(1) || 不支持
 |-
-| 区间更新 || <math>O(n)</math> || <math>O(1)</math>
+| 区间修改 || 不支持 || O(1)
 |}
-== 进阶思考 ==
+== 进阶技巧 ==
-* 如何结合前缀和与差分处理动态数组？
+* '''前缀和+哈希表'''：解决子数组和等于特定值的问题（如LeetCode 560题）
-* 三维场景下的前缀和与差分如何实现？
+* '''差分+离散化'''：处理大规模稀疏区间问题
-* 在树状结构（如二叉树）中是否有类似技巧？
+* '''多维推广'''：三维及更高维度的前缀和应用（如立体空间体积计算）
+{{Tip|前缀和与差分常组合使用，例如先差分修改再前缀和查询，或在动态维护中交替应用。}}
-{{Tip|前缀和与差分是许多高级算法（如快速傅里叶变换）的基础组件，掌握它们能显著提升算法设计能力。}}
+== 参见 ==
+* [[滑动窗口]]
+* [[树状数组]]
+* [[线段树]]
 [[Category:计算机科学]]
-[[Category:数据结构与算法]]
+[[Category:面试技巧]]
-[[Category:算法设计技巧]]
+[[Category:算法基础]]