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

{{Note|本条目详细介绍算法设计中的'''前缀和与差分'''技术，适用于初学者及需要巩固该概念的程序员。内容包含基础原理、代码实现、实际应用及复杂度分析。}}

== 概述 ==
'''前缀和（Prefix Sum）'''与'''差分（Difference Array）'''是两种互补的算法设计技巧，常用于高效处理'''区间查询'''和'''区间更新'''问题。前缀和通过预处理数组实现快速区间求和，而差分则通过标记变化实现高效区间修改。

=== 核心思想 ===
* '''前缀和'''：将原始数组转换为前<math>i</math>项和的数组，使得区间和查询可在<math>O(1)</math>时间内完成。
* '''差分'''：记录相邻元素的差值，通过累加差分数组还原原数组，使区间增减操作降为<math>O(1)</math>时间复杂度。

== 前缀和 ==
=== 一维前缀和 ===
给定数组<math>A[0..n-1]</math>，其前缀和数组<math>S</math>定义为：
<math>S[i] = \sum_{k=0}^{i} A[k] \quad \text{其中} \ S[-1]=0</math>

==== 代码实现 ====
<syntaxhighlight lang="python">
def prefix_sum(arr):
    n = len(arr)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + arr[i]
    return prefix

# 示例
arr = [3, 1, 4, 1, 5]
prefix = prefix_sum(arr)
print(prefix)  # 输出: [0, 3, 4, 8, 9, 14]
</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>S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j]</math>

== 差分 ==
=== 一维差分 ===
差分数组<math>D</math>满足：
<math>D[i] = A[i] - A[i-1] \quad \text{（假设} \ A[-1]=0 \text{）}</math>

==== 区间更新 ===
对原数组<math>A[l..r]</math>增加<math>k</math>，只需：
* <math>D[l] += k</math>
* <math>D[r+1] -= k</math>

==== 代码示例 ====
<syntaxhighlight lang="python">
def difference_array(arr):
    n = len(arr)
    diff = [0] * (n + 1)
    diff[0] = arr[0]
    for i in range(1, n):
        diff[i] = arr[i] - arr[i - 1]
    return diff

def apply_diff(diff, l, r, k):
    diff[l] += k
    if r + 1 < len(diff):
        diff[r + 1] -= k

# 示例
arr = [1, 2, 3, 4, 5]
diff = difference_array(arr)
apply_diff(diff, 1, 3, 2)  # 对arr[1..3]增加2
# 还原数组
for i in range(1, len(arr)):
    diff[i] += diff[i - 1]
print(diff[:-1])  # 输出: [1, 4, 5, 6, 5]
</syntaxhighlight>

=== 二维差分 ===
类似地，二维差分可通过四个角点操作实现矩形区域的增减。

== 应用案例 ==
=== 案例1：子数组和等于K ===
'''问题'''：统计数组中连续子数组和为<math>K</math>的数量。<br>
'''解法'''：利用前缀和+哈希表，时间复杂度<math>O(n)</math>。

=== 案例2：航班预订统计 ===
'''问题'''：处理<math>n</math>次航班预订，每次预订从<math>i</math>到<math>j</math>的<math>k</math>个座位，求最终每班次的座位数。<br>
'''解法'''：差分数组模拟预订操作后还原。

<mermaid>
graph LR
    A[原始数组] -->|预处理| B[前缀和数组]
    B -->|O(1)查询| C[区间和]
    D[差分数组] -->|O(1)更新| E[区间增减]
    E -->|还原| A
</mermaid>

== 复杂度分析 ==
{| class="wikitable"
|+ 时间复杂度对比
! 操作 !! 原始数组 !! 前缀和/差分
|-
| 区间查询 || <math>O(n)</math> || <math>O(1)</math>
|-
| 区间更新 || <math>O(n)</math> || <math>O(1)</math>
|}

== 进阶思考 ==
* 如何结合前缀和与差分处理动态数组？
* 三维场景下的前缀和与差分如何实现？
* 在树状结构（如二叉树）中是否有类似技巧？

{{Tip|前缀和与差分是许多高级算法（如快速傅里叶变换）的基础组件，掌握它们能显著提升算法设计能力。}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:算法设计技巧]]