题解 | #【模板】差分#

题目链接

题目描述

对于给定的长度为 $n$ 的数组 $a$ ，我们有 $m$ 次修改操作，每一次操作给出三个参数 $l, r, v$ ，代表将数组中的元素 $a_l, a_{l+1}, \dots, a_r$ 都加上 $v$ 。请你输出全部操作完成后的数组。

解题思路

本题要求对数组进行多次区间修改。如果每次修改都遍历区间 $[l, r]$ 并更新其中的每一个元素，单次操作的时间复杂度为 $O(n)$ ，总复杂度将达到 $O(n \cdot m)$ ，在数据量较大时会超时。

为了优化区间修改操作，我们可以引入差分数组（Difference Array）。

1. 什么是差分数组？

差分数组 $d$ 是原始数组 $a$ 的一种转换形式。我们定义：

$d_1 = a_1$
$d_i = a_i - a_{i-1}$ (对于 $i > 1$ )

差分数组有一个非常重要的性质：原始数组 $a$ 是差分数组 $d$ 的前缀和。即 $a_i = \sum_{k=1}^{i} d_k$ 。

2. 差分如何优化区间修改？

一个对区间 $[l, r]$ 中所有元素都加上 $v$ 的操作，在差分数组上会产生什么影响？

对于 $i < l$ ： $a_i$ 和 $a_{i-1}$ 都没有变，所以 $d_i$ 不变。
对于 $i = l$ ： $a_l$ 增加了 $v$ ，而 $a_{l-1}$ 不变。因此 $d_l = (a_l + v) - a_{l-1} = (a_l - a_{l-1}) + v$ 。可见 $d_l$ 的值增加了 $v$ 。
对于 $l < i \le r$ ： $a_i$ 和 $a_{i-1}$ 都增加了 $v$ 。因此 $d_i = (a_i+v) - (a_{i-1}+v) = a_i - a_{i-1}$ 。可见 $d_i$ 的值不变。
对于 $i = r + 1$ ： $a_{r+1}$ 不变，而 $a_r$ 增加了 $v$ 。因此 $d_{r+1} = a_{r+1} - (a_r+v) = (a_{r+1} - a_r) - v$ 。可见 $d_{r+1}$ 的值减少了 $v$ 。
对于 $i > r + 1$ ： $a_i$ 和 $a_{i-1}$ 都没有变，所以 $d_i$ 不变。

结论：对原数组 $a$ 的区间 $[l, r]$ 加上值 $v$ ，等价于只对差分数组 $d$ 进行两个单点修改：

$d_l = d_l + v$
$d_{r+1} = d_{r+1} - v$ (需注意边界，当 $r+1 > n$ 时，此操作不需要)

3. 算法流程

构建初始差分数组：根据原始数组 $a$ 计算出初始的差分数组 $d$ 。这需要 $O(n)$ 时间。
处理所有修改：对于 $m$ 次操作，每次操作都只修改差分数组的两个点。这需要 $O(m)$ 时间。
还原最终数组：所有修改操作完成后，通过计算差分数组的前缀和，还原出最终的数组 $a$ 。这需要 $O(n)$ 时间。

通过这种方法，我们将总时间复杂度从 $O(n \cdot m)$ 优化到了 $O(n+m)$ 。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

int main() {
    int n, m;
    cin >> n >> m;

    vector<LL> a(n + 1);
    // 差分数组，大小设为 n+2 以便处理 d[r+1]
    vector<LL> d(n + 2, 0);

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        // 构建初始差分数组
        d[i] = a[i] - a[i - 1];
    }

    for (int k = 0; k < m; ++k) {
        int l, r;
        LL v;
        cin >> l >> r >> v;
        // 区间修改等价于对差分数组的两个点进行修改
        d[l] += v;
        d[r + 1] -= v;
    }

    // 通过前缀和还原最终数组
    for (int i = 1; i <= n; ++i) {
        a[i] = a[i - 1] + d[i];
    }

    // 输出结果
    for (int i = 1; i <= n; ++i) {
        cout << a[i] << (i == n ? "" : " ");
    }
    cout << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        long[] a = new long[n + 1];
        // 差分数组，大小设为 n+2 以便处理 d[r+1]
        long[] d = new long[n + 2];

        // 构建初始差分数组
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextLong();
            d[i] = a[i] - a[i - 1];
        }
        
        // 处理m次修改
        for (int k = 0; k < m; k++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            long v = sc.nextLong();
            // 区间修改等价于对差分数组的两个点进行修改
            d[l] += v;
            d[r + 1] -= v;
        }

        // 通过前缀和还原最终数组并输出
        for (int i = 1; i <= n; i++) {
            a[i] = a[i - 1] + d[i];
            System.out.print(a[i] + (i == n ? "" : " "));
        }
        System.out.println();
    }
}

# 读取 n 和 m
n, m = map(int, input().split())
# 读取原始数组 (0-based)
a = list(map(int, input().split()))

# 差分数组 (1-based for easier logic)
# 大小为 n+2 以便处理 d[r+1]
d = [0] * (n + 2)

# 构建初始差分数组
d[1] = a[0]
for i in range(1, n):
    d[i+1] = a[i] - a[i-1]

# 处理m次修改
for _ in range(m):
    l, r, v = map(int, input().split())
    # 区间修改等价于对差分数组的两个点进行修改
    d[l] += v
    d[r + 1] -= v

# 通过前缀和还原最终数组
result = [0] * n
result[0] = d[1]
for i in range(1, n):
    result[i] = result[i-1] + d[i+1]

# 输出结果
print(*result)

算法及复杂度

算法：差分 (Difference Array)
时间复杂度： $O(n + m)$ 。其中 $O(n)$ 用于构建初始差分数组， $O(m)$ 用于处理 $m$ 次修改（每次 $O(1)$ ），最后 $O(n)$ 用于从差分数组还原最终结果。
空间复杂度： $O(n)$ ，用于存储差分数组。