前缀和与差分

概述

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

核心思想

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

前缀和

一维前缀和

给定数组 $A [0 . . n - 1]$ ，其前缀和数组 $S$ 定义为： $S [i] = \sum_{k = 0}^{i} A [k] 其中 S [- 1] = 0$

代码实现

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]

= 区间查询

查询区间 $[l, r]$ 的和： $S [r + 1] - S [l]$ （注意Python中数组从0开始索引）。

二维前缀和

扩展至二维矩阵，定义 $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]$

差分

一维差分

差分数组 $D$ 满足： $D [i] = A [i] - A [i - 1] （假设 A [- 1] = 0 ）$

= 区间更新

对原数组 $A [l . . r]$ 增加 $k$ ，只需：

$D [l] + = k$
$D [r + 1] - = k$

代码示例

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]

二维差分

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

应用案例

案例1：子数组和等于K

问题：统计数组中连续子数组和为 $K$ 的数量。
解法：利用前缀和+哈希表，时间复杂度 $O (n)$ 。

案例2：航班预订统计

问题：处理 $n$ 次航班预订，每次预订从 $i$ 到 $j$ 的 $k$ 个座位，求最终每班次的座位数。
解法：差分数组模拟预订操作后还原。

复杂度分析

时间复杂度对比
操作	原始数组	前缀和/差分
区间查询	$O (n)$	$O (1)$
区间更新	$O (n)$	$O (1)$

进阶思考

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

模板:Tip