差分数组

差分数组是一种用于高效处理区间更新问题的数据结构。它的核心思想是通过维护一个差分数组来记录每个位置的变化量，从而在常数时间内完成区间更新操作。

基本概念

给定一个初始数组 A，差分数组 D 的定义如下：

D[0] = A[0]
D[i] = A[i] - A[i-1]，对于 i > 0

通过差分数组 D，我们可以快速地对原数组 A 的某个区间 [l, r] 进行增量更新。假设我们要将区间 [l, r] 中的每个元素增加 x，我们只需进行以下操作：

D[l] += x
D[r+1] -= x（如果 r+1 在数组范围内）

还原原数组

在完成所有的区间更新后，我们可以通过差分数组 D 还原出更新后的原数组 A。具体步骤如下：

A[0] = D[0]
A[i] = A[i-1] + D[i]，对于 i > 0

示例

假设我们有一个初始数组 A = [0, 0, 0, 0, 0]，我们希望进行以下区间更新：

将区间 [1, 3] 中的每个元素增加 2
将区间 [2, 4] 中的每个元素增加 3

差分数组的构建与更新

初始差分数组 D 为 [0, 0, 0, 0, 0, 0]。

对于第一个更新操作 [1, 3] 增加 2：
- D[1] += 2，所以 D 变为 [0, 2, 0, 0, 0, 0]
- D[4] -= 2，所以 D 变为 [0, 2, 0, 0, -2, 0]
对于第二个更新操作 [2, 4] 增加 3：
- D[2] += 3，所以 D 变为 [0, 2, 3, 0, -2, 0]
- D[5] -= 3，所以 D 变为 [0, 2, 3, 0, -2, -3]

还原更新后的数组

通过累加差分数组 D，我们可以得到更新后的数组 A：

A[0] = D[0] = 0
A[1] = A[0] + D[1] = 0 + 2 = 2
A[2] = A[1] + D[2] = 2 + 3 = 5
A[3] = A[2] + D[3] = 5 + 0 = 5
A[4] = A[3] + D[4] = 5 - 2 = 3

因此，更新后的数组为 [0, 2, 5, 5, 3]。

示例代码

以下是一个简单的 Python 示例代码，演示如何使用差分数组进行区间更新：

def apply_updates(n, updates):
    # 初始化数组和差分数组
    A = [0] * n
    D = [0] * (n + 1)

    # 应用所有更新
    for l, r, x in updates:
        D[l] += x
        if r + 1 < n:
            D[r + 1] -= x

    # 还原更新后的数组
    A[0] = D[0]
    for i in range(1, n):
        A[i] = A[i - 1] + D[i]

    return A

# 示例使用
n = 5
updates = [(1, 3, 2), (2, 4, 3)]
result = apply_updates(n, updates)
print(result)  # 输出: [0, 2, 5, 5, 3]

应用场景

差分数组在需要频繁进行区间更新的场景中非常有用，例如：

区间加法
区间乘法
区间赋值

通过差分数组，我们可以将这些操作的时间复杂度从 O(n) 降低到 O(1)，从而显著提高效率。