编辑“︁前缀和与差分”︁

{{Note|本条目将详细介绍算法中的'''前缀和'''与'''差分'''技术，包含基础概念、实现方法及实际应用案例。}}

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

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

两者关系如下图所示：
<mermaid>
graph LR
    A[原数组] -->|预处理| B[前缀和数组]
    A -->|相邻元素差值| C[差分数组]
    B -->|逆运算| C
    C -->|前缀和运算| A
</mermaid>

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

==== 代码实现 ====
<syntaxhighlight lang="python">
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)
</syntaxhighlight>

=== 二维前缀和 ===
对于二维数组<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
        2 4 6
        7 8 9]] --> B[["0 0 0 0
                       0 1 4 9
                       0 3 9 17
                       0 10 24 42"]]
</mermaid>

== 差分 ==
=== 一维差分 ===
给定数组<math>A[0..n-1]</math>，其差分数组<math>D</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>D[l] += k,\ D[r+1] -= k</math>

==== 代码示例 ====
<syntaxhighlight lang="python">
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]
</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：区间统计 ===
'''问题'''：给定学生每日学习时长记录，快速回答任意时间段内的总学习时长。<br>
'''解决方案'''：使用前缀和数组预处理。

=== 案例2：航班预订统计 ===
'''问题'''：有n个航班，每个预订记录包含<math>[first, last, seats]</math>，求最终每个航班的座位数。<br>
'''解决方案'''：使用差分数组处理区间增减，最后还原数组。

<syntaxhighlight lang="python">
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]
</syntaxhighlight>

== 复杂度分析 ==
{| class="wikitable"
|+ 操作复杂度对比
! 操作 !! 前缀和 !! 差分
|-
| 预处理 || O(n) || O(n)
|-
| 单点查询 || O(1) || O(n)
|-
| 区间查询 || O(1) || 不支持
|-
| 区间修改 || 不支持 || O(1)
|}

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

{{Tip|前缀和与差分常组合使用，例如先差分修改再前缀和查询，或在动态维护中交替应用。}}

== 参见 ==
* [[滑动窗口]]
* [[树状数组]]
* [[线段树]]

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:算法基础]]