Tommy Chen home

前缀和与差分

10 Sep 2024

1. 简介

前缀和与差分是一对非常常用的技巧。它们都把“区间”问题转换成“单点”问题：

前缀和适合处理多次区间查询。
差分适合处理多次区间修改。

当数组规模很大、操作次数很多时，逐个遍历区间通常会超时。前缀和和差分能把一次区间操作从 O(n) 降到 O(1)，最后再用一次 O(n) 的扫描得到结果。

两者的区别在于“把工作提前到什么时候做”。前缀和先花一次 O(n) 的时间保存累计结果，之后每次查询都很快；差分则先把每次修改记在边界上，等所有修改结束后再统一还原。读题时先看清楚：题目是不断询问区间，还是不断修改区间？

2. 前缀和

2.1 原理

设原数组为 a[1], a[2], ..., a[n]。定义前缀和数组 s：

s[0] = 0
s[i] = s[i - 1] + a[i]

其中 s[i] 表示前 i 个数的和。这样，区间 [l, r] 的和可以写成：

a[l] + a[l + 1] + ... + a[r] = s[r] - s[l - 1]

例如数组为 [2, 1, 3, 4, 2]，则前缀和为 [0, 2, 3, 6, 10, 12]。要求区间 [2, 4] 的和，不必重新计算 1 + 3 + 4，只需计算 s[4] - s[1] = 10 - 2 = 8。

这个减法的本质是“消去前面不需要的部分”。s[r] 包含从第 1 个数到第 r 个数，而 s[l - 1] 恰好包含从第 1 个数到第 l - 1 个数；相减后留下的就是 l 到 r。这也是代码中把 s[0] 设为 0 的原因：当 l 为 1 时，公式仍然可以直接使用，不需要单独分类讨论。

2.2 区间和查询

下面的程序先读入数组，再回答 q 次区间求和询问。预处理前缀和需要 O(n)，每次询问只需要 O(1)。

#include <bits/stdc++.h>
using namespace std;

const int N = 100000 + 10;
long long a[N], s[N];

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

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << '\n';
    }
    return 0;
}

这里使用 long long 保存前缀和。即使单个元素没有超过 int 的范围，很多个元素相加后也可能溢出。

前缀和的代价是：原数组一旦发生修改，后面的很多前缀和都可能改变。因此它最适合“先读入数组，再大量查询”的静态场景。

3. 差分

3.1 原理

差分数组记录相邻元素的变化。定义：

d[1] = a[1]
d[i] = a[i] - a[i - 1]  (i > 1)

对差分数组做一次前缀和，就可以恢复原数组：

a[i] = d[1] + d[2] + ... + d[i]

差分最重要的用途是区间加法。若要给 [l, r] 中的每个数加上 v，只需：

d[l] += v
d[r + 1] -= v

为什么有效？从 l 开始，前缀和比原来多了 v；到 r + 1 时又减去 v，所以影响刚好停在 r。这样每次区间修改只需 O(1)。

例如原数组为 [3, 5, 2, 6, 4]，它的差分为 [3, 2, -3, 4, -2]。若给区间 [2, 4] 都加 10，只改两个位置：d[2] += 10、d[5] -= 10，差分变为 [3, 12, -3, 4, -12]。对它求前缀和，便得到 [3, 15, 12, 16, 4]，正好只有第 2 到第 4 个数增加了 10。

这里的 r + 1 可能等于 n + 1，所以数组要比实际长度多开一个位置；恢复结果时只需遍历到 n。

3.2 例子：区间加法后求最小值

下面的例子先用差分数组读入初始成绩，再进行多次区间加分。所有修改完成后，用前缀和还原每个人的最终成绩，并求最小值。

读入初始数组时，代码使用 d[i] += x、d[i + 1] -= x。这等价于把“第 i 个位置单独加 x”看作区间 [i, i] 的修改。这样就不必先单独建立原数组的差分，初始数据和后续修改可以统一处理。

#include <bits/stdc++.h>
using namespace std;

const int N = 5000000 + 20;
long long d[N];

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

    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        d[i] += x;
        d[i + 1] -= x;
    }

    while (q--) {
        int l, r;
        long long v;
        cin >> l >> r >> v;
        d[l] += v;
        d[r + 1] -= v;
    }

    long long answer = LLONG_MAX;
    for (int i = 1; i <= n; i++) {
        d[i] += d[i - 1];
        answer = min(answer, d[i]);
    }

    cout << answer;
    return 0;
}

4. 如何选择

多次询问区间和，数组基本不修改：使用前缀和。
多次给区间整体加值，最后统一输出：使用差分。

普通差分适用于“修改完成后统一还原”。如果每次修改后都要立刻得到新数组的区间和，就不属于这篇文章讨论的基础场景了。

前缀和与差分看起来简单，但它们建立了一个重要思路：不直接处理整个区间，而是通过预处理和边界变化来表示区间。这也是许多高效数据结构的基础。

前缀和与差分

Related Posts