跳到主要内容

前缀和与差分

前缀和与差分是算法中常用的两种技巧，它们能够高效地处理数组区间操作问题。本文将从基础概念入手，逐步讲解它们的原理、实现方法以及实际应用。

1. 什么是前缀和？​

前缀和（Prefix Sum）是指将数组中每个位置的值替换为从数组开头到当前位置的所有元素的和。通过前缀和，我们可以快速计算任意区间的和。

1.1 前缀和的构建​

假设有一个数组 arr，其前缀和数组 prefix 的定义如下：

prefix[i] = arr[0] + arr[1] + ... + arr[i]

例如，给定数组 arr = [1, 2, 3, 4, 5]，其前缀和数组为 prefix = [1, 3, 6, 10, 15]。

1.2 前缀和的应用​

前缀和的主要应用是快速计算任意区间的和。例如，如果我们想计算 arr 中从索引 l 到 r 的和，可以使用以下公式：

sum(l, r) = prefix[r] - prefix[l - 1]
备注

注意：当 l = 0 时，sum(0, r) = prefix[r]。

1.3 代码示例​

以下是一个计算前缀和的 Python 示例：

def prefix_sum(arr):
    prefix = [0] * len(arr)
    prefix[0] = arr[0]
    for i in range(1, len(arr)):
        prefix[i] = prefix[i - 1] + arr[i]
    return prefix

arr = [1, 2, 3, 4, 5]
prefix = prefix_sum(arr)
print(prefix)  # 输出: [1, 3, 6, 10, 15]

2. 什么是差分？​

差分（Difference）是前缀和的逆操作。差分数组 diff 的每个元素表示原数组 arr 中相邻元素的差值。通过差分数组，我们可以高效地对数组的某个区间进行增减操作。

2.1 差分的构建​

给定数组 arr，其差分数组 diff 的定义如下：

diff[i] = arr[i] - arr[i - 1]  (i > 0)
diff[0] = arr[0]               (i = 0)

例如，给定数组 arr = [1, 3, 6, 10, 15]，其差分数组为 diff = [1, 2, 3, 4, 5]。

2.2 差分的应用​

差分的主要应用是对数组的某个区间进行增减操作。例如，如果我们想对 arr 中从索引 l 到 r 的所有元素增加 val，可以通过以下步骤实现：

  1. 对差分数组 diff 进行修改： 
    diff[l] += val
    diff[r + 1] -= val  (如果 r + 1 < len(diff))
  2. 通过差分数组还原原数组。

2.3 代码示例​

以下是一个使用差分数组进行区间增减操作的 Python 示例：

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

def restore_arr(diff):
    arr = [0] * len(diff)
    arr[0] = diff[0]
    for i in range(1, len(diff)):
        arr[i] = arr[i - 1] + diff[i]
    return arr

diff = [1, 2, 3, 4, 5]
apply_diff(diff, 1, 3, 10)
arr = restore_arr(diff)
print(arr)  # 输出: [1, 13, 16, 19, 5]

3. 实际应用场景​

3.1 区间求和问题​

前缀和常用于解决区间求和问题。例如，给定一个数组和多个查询，每个查询要求计算某个区间的和。使用前缀和可以在 O(1) 时间内回答每个查询。

3.2 区间增减问题​

差分常用于解决区间增减问题。例如，给定一个数组和多个操作，每个操作要求对某个区间的所有元素增加一个值。使用差分可以在 O(1) 时间内完成每个操作。

4. 总结​

前缀和与差分是处理数组区间操作的高效工具。前缀和用于快速计算区间和，而差分用于高效地进行区间增减操作。掌握这两种技巧可以帮助你解决许多与数组相关的算法问题。

5. 附加资源与练习​

  • 练习 1：给定一个数组 arr 和多个查询，每个查询要求计算从索引 l 到 r 的和。请使用前缀和实现。
  • 练习 2：给定一个数组 arr 和多个操作，每个操作要求对从索引 l 到 r 的所有元素增加 val。请使用差分实现。
提示

提示：在实际编程中，前缀和与差分常常结合使用，以解决更复杂的问题。