题解 | #【模板】差分#

题目链接

【模板】差分

题目描述

给定一个长度为 $n$ 的数组，有 $q$ 次修改操作，每次操作将指定区间 $[l, r]$ 内的所有元素都加上一个值 $c$ 。求所有操作完成后的最终数组。

解题思路

本题的核心在于需要对数组进行频繁的区间修改。如果每次修改都遍历 $[l, r]$ 区间，那么 $q$ 次操作的总时间复杂度将是 $O(q \cdot n)$ ，在 $n$ 和 $q$ 都很大的情况下会超时。

为了高效地处理区间修改，我们可以引入差分数组。

什么是差分？ 差分是前缀和的逆运算。对于一个原数组 $A$ ，它的差分数组 $B$ 定义为： $B[i] = A[i] - A[i-1]$ 特别地，我们定义 $B[1] = A[1]$ 。

从差分数组 $B$ 反推原数组 $A$ ，只需要对 $B$ 求前缀和即可： $A[i] = \sum_{j=1}^{i} B[j]$

差分如何优化区间修改？ 差分数组最强大的特性在于，对原数组 $A$ 的一个区间 $[l, r]$ 加上一个值 $c$ ，仅仅需要对差分数组 $B$ 进行两次单点修改：

$B[l]$ 增加 $c$ ：这会导致从 $A[l]$ 开始的所有元素（ $A[l], A[l+1], \dots$ ）在计算前缀和时都增加了 $c$ 。
$B[r+1]$ 减少 $c$ ：为了抵消在 $r$ 之后的位置上多加的 $c$ ，我们需要在 $B[r+1]$ 处减去 $c$ 。这会使得从 $A[r+1]$ 开始的所有元素（ $A[r+1], A[r+2], \dots$ ）在计算前缀和时都减去了 $c$ 。

这样，两次单点修改的效果叠加起来，就精确地实现了只对区间 $[l, r]$ 加上 $c$ 的操作。

算法步骤：

读入初始数组 $A$ 。
创建一个差分数组 $B$ 。我们可以创建一个只记录变化量的差分数组，因此初始时全为 0。
对于每一次操作 $(l, r, c)$ ，我们对差分数组进行修改： $B[l] += c$ 并且 $B[r+1] -= c$ 。
所有 $q$ 次操作完成后，对差分数组 $B$ 求前缀和，得到每个位置上的总变化量。
将这个总变化量加到原数组 $A$ 的对应位置上，即可得到最终的数组。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 差分数组，b[i] 记录的是 a[i] 相对于 a[i-1] 的增量所发生的变化
    // 多开一个位置防止 r+1 越界
    vector<long long> b(n + 2, 0);

    while (q--) {
        int l, r;
        long long c;
        cin >> l >> r >> c;
        // 数组下标从1开始，需要转换为0-indexed
        b[l - 1] += c;
        b[r] -= c;
    }

    // 通过前缀和计算每个位置的总增量
    for (int i = 1; i < n; ++i) {
        b[i] += b[i - 1];
    }

    // 将增量加到原数组上
    for (int i = 0; i < n; ++i) {
        a[i] += b[i];
    }

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

    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 q = sc.nextInt();

        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        // 差分数组，用于记录变化量
        long[] b = new long[n + 1];

        for (int i = 0; i < q; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            long c = sc.nextLong();
            // 题目下标从1开始，转换为0-indexed
            b[l - 1] += c;
            if (r < n) {
                b[r] -= c;
            }
        }

        // 计算每个位置的总增量
        long current_change = 0;
        for (int i = 0; i < n; i++) {
            current_change += b[i];
            a[i] += current_change;
        }

        // 输出结果
        for (int i = 0; i < n; i++) {
            System.out.print(a[i] + (i == n - 1 ? "" : " "));
        }
        System.out.println();
    }
}

import sys

def main():
    n, q = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    
    # 差分数组，用于记录变化量
    b = [0] * (n + 1)
    
    # 处理所有操作，更新差分数组
    for _ in range(q):
        l, r, c = map(int, sys.stdin.readline().split())
        # 题目下标从1开始，转换为0-indexed
        b[l - 1] += c
        if r < n:
            b[r] -= c
            
    # 计算每个位置的总增量并更新原数组
    current_change = 0
    for i in range(n):
        current_change += b[i]
        a[i] += current_change
        
    # 输出结果
    print(*a)

if __name__ == "__main__":
    main()

算法及复杂度

算法：差分
时间复杂度： $O(n+q)$ 。其中 $q$ 次操作每次都只修改差分数组的两个点，共 $O(q)$ 。最后通过一次遍历还原最终数组，需要 $O(n)$ 。
空间复杂度： $O(n)$ ，用于存储差分数组。