前缀和与差分

概述

前缀和（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

参见