【模板】差分

思路

拿到这题，最直接的想法是什么？每次操作都遍历 [l, r]，把每个元素加上 c。这样每次操作是 ，总共 次就是 ，数据一大肯定超时。

那有没有办法让每次"区间加"变成 ？

这就要用到差分数组了。差分是前缀和的逆运算——前缀和是"求区间和"的利器，差分就是"区间修改"的利器。

什么是差分数组？

定义差分数组 d[]，其中 d[i] = a[i] - a[i-1]（d[1] = a[1]）。差分数组有一个关键性质：对 d 做前缀和，就能还原出原数组 a。

差分怎么实现"区间加"？

想给 a[l] 到 a[r] 都加上 c，只需要：

  • d[l] += c：从第 l 个位置开始，前缀和就会多出 c
  • d[r+1] -= c：从第 r+1 个位置开始，把多出的 c 抵消掉

就这两步， 搞定一次区间修改。所有操作做完之后，对差分数组求一次前缀和，就得到最终的原数组了。

整理一下流程：

  1. 读入原数组，构建差分数组
  2. 对每次操作，修改差分数组的两个位置
  3. 最后对差分数组求前缀和，输出结果

注意 r+1 可能越界（当 r == n 时），所以要判断一下 r+1 <= n 再操作，或者把数组多开一格。

代码

#include <cstdio>
using namespace std;

const int MAXN = 1000005;
long long a[MAXN], d[MAXN];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    // 构建差分数组
    for (int i = 1; i <= n; i++) {
        d[i] = a[i] - a[i - 1];
    }
    // 处理每次操作
    for (int i = 0; i < m; i++) {
        int l, r;
        long long c;
        scanf("%d%d%lld", &l, &r, &c);
        d[l] += c;
        if (r + 1 <= n) d[r + 1] -= c;
    }
    // 前缀和还原
    for (int i = 1; i <= n; i++) {
        d[i] += d[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        if (i > 1) printf(" ");
        printf("%lld", d[i]);
    }
    printf("\n");
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st = new StreamTokenizer(br);
        StringBuilder sb = new StringBuilder();

        st.nextToken(); int n = (int) st.nval;
        st.nextToken(); int m = (int) st.nval;

        long[] d = new long[n + 2];
        long[] a = new long[n + 1];

        for (int i = 1; i <= n; i++) {
            st.nextToken();
            a[i] = (long) st.nval;
        }
        // 构建差分数组
        for (int i = 1; i <= n; i++) {
            d[i] = a[i] - a[i - 1];
        }
        // 处理每次操作
        for (int i = 0; i < m; i++) {
            st.nextToken(); int l = (int) st.nval;
            st.nextToken(); int r = (int) st.nval;
            st.nextToken(); long c = (long) st.nval;
            d[l] += c;
            if (r + 1 <= n) d[r + 1] -= c;
        }
        // 前缀和还原
        for (int i = 1; i <= n; i++) {
            d[i] += d[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            if (i > 1) sb.append(' ');
            sb.append(d[i]);
        }
        System.out.println(sb.toString());
    }
}

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    d = [0] * (n + 2)
    for i in range(1, n + 1):
        d[i] = a[i] - a[i - 1]
    for _ in range(m):
        parts = input().split()
        l, r, c = int(parts[0]), int(parts[1]), int(parts[2])
        d[l] += c
        if r + 1 <= n:
            d[r + 1] -= c
    for i in range(1, n + 1):
        d[i] += d[i - 1]
    print(' '.join(map(str, d[1:n+1])))

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    let idx = 0;
    const [n, m] = lines[idx++].split(' ').map(Number);
    const a = [0, ...lines[idx++].split(' ').map(Number)];
    const d = new Array(n + 2).fill(0);
    for (let i = 1; i <= n; i++) {
        d[i] = a[i] - a[i - 1];
    }
    for (let i = 0; i < m; i++) {
        const parts = lines[idx++].split(' ').map(Number);
        const l = parts[0], r = parts[1], c = parts[2];
        d[l] += c;
        if (r + 1 <= n) d[r + 1] -= c;
    }
    for (let i = 1; i <= n; i++) {
        d[i] += d[i - 1];
    }
    console.log(d.slice(1, n + 1).join(' '));
});

复杂度分析

  • 时间复杂度: ，构建差分数组 ，处理 次操作每次 ，最后前缀和还原 。
  • 空间复杂度: ，存储差分数组。

小结

差分和前缀和是一对互逆操作：前缀和擅长快速求区间和（ 查询），差分擅长快速做区间修改（ 修改）。记住差分的核心操作就两行——d[l] += c 和 d[r+1] -= c，修改完之后做一次前缀和就还原了。这个模板是很多高级算法（树上差分、二维差分等）的基础，务必掌握。