前缀和 & 差分

一对对偶操作

前缀和(Prefix Sum)和差分(Difference)是互逆的:

差分→前缀和原数组,原数组→差分差分数组\text{差分} \xrightarrow{\text{前缀和}} \text{原数组}, \qquad \text{原数组} \xrightarrow{\text{差分}} \text{差分数组}

原数组 a:  1  3  2  5  4
前缀和 s:  1  4  6 11 15      ← s[i] = a[0..i] 的和
差分   d:  1  2 -1  3 -1      ← d[i] = a[i] - a[i-1]
擅长单次操作
前缀和区间求和O(1)O(1)预处理O(n)O(n)
差分区间加O(1)O(1)最后前缀和还原O(n)O(n)

核心口诀:

多次查询区间和 → 前缀和;多次区间修改 → 差分。

一维前缀和

定义

s[i]=∑k=0ia[k]s[i] = \sum_{k=0}^{i} a[k]

vector<long long> s(n + 1, 0);      // s[0] = 0,1-indexed 更方便
for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i - 1];

// 查询 [l, r] 的和(1-indexed)
long long sum(int l, int r) { return s[r] - s[l - 1]; }

为什么留 s[0] = 0:这样查询 [1, r] 就是 s[r] - s[0],不用特判l=1l = 1 的边界。

a:      [a1][a2][a3][a4][a5]
s:   [0][a1][a1+a2][...][a1..a5]

sum(2,4) = s[4] - s[1] = (a1+a2+a3+a4) - (a1) = a2+a3+a4  ✓

应用

问题做法
区间和查询(静态)直接前缀和
平均值最大的子数组前缀和 + 单调性 / 二分
和为 k 的子数组个数前缀和 + 哈希表计数
是否存在和为 0 的子数组前缀和 + 集合(两前缀和相等 ⟺ 中间和为 0)

和为 k 的子数组个数

// sum(i, j] = s[j] - s[i] = k  ⟺  s[i] = s[j] - k
long long count_subarray_sum(vector<int>& a, int k) {
    unordered_map<long long, int> cnt;
    cnt[0] = 1;                 // s[0] = 0 先放进去
    long long s = 0, ans = 0;
    for (int x : a) {
        s += x;
        ans += cnt[s - k];      // 有多少个 s[i] == s - k
        cnt[s]++;
    }
    return ans;
}

关键:cnt[0] = 1。否则会漏掉"从第 0 个元素开始"的子数组。

为什么能用哈希表:我们只关心"之前出现过几次某个前缀和值",不关心位置。这是O(n)O(n) 而不是O(n2)O(n^2)。

二维前缀和

定义

s[i][j]=∑x≤i, y≤ja[x][y]s[i][j] = \sum_{x \le i,\, y \le j} a[x][y]

即从(1,1)(1,1) 到(i,j)(i,j) 的矩形和。

构造(容斥)

s[i][j]=a[i][j]+s[i−1][j]+s[i][j−1]−s[i−1][j−1]s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1]

┌───────────┬─────┐
│           │     │
│  s[i-1][j]│ s[i][j-1] 部分
│           │     │
├───────────┼─────┤   ← 重叠的 s[i-1][j-1] 被加了两次,减掉一次
│           │ a[i][j] │
└───────────┴─────────┘

查询子矩阵(x1,y1)(x_1,y_1) 到(x2,y2)(x_2,y_2)

sum=s[x2][y2]−s[x1−1][y2]−s[x2][y1−1]+s[x1−1][y1−1]\text{sum} = s[x_2][y_2] - s[x_1-1][y_2] - s[x_2][y_1-1] + s[x_1-1][y_1-1]

vector<vector<long long>> s(n + 1, vector<long long>(m + 1, 0));
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];

long long query(int x1, int y1, int x2, int y2) {
    return s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
}

画个图就清楚了:大矩形减去上面和左边,被减两次的左上角加回来。

一维差分

定义

d[i]=a[i]−a[i−1](令 a[−1]=0)d[i] = a[i] - a[i-1] \quad (\text{令 } a[-1] = 0)

性质:对dd 求前缀和就还原回aa:

a[i]=∑k=0id[k]a[i] = \sum_{k=0}^{i} d[k]

区间加

要给[l,r][l, r] 全部+v+v:

d[l]   += v      ← 从这里开始,后面所有元素都 +v
d[r+1] -= v      ← 到 r+1 抵消,后面的不受影响
// 多次区间加,最后一次性还原
vector<long long> d(n + 2, 0);      // 多开 1 个位置给 r+1
void add(int l, int r, long long v) {   // 0-indexed
    d[l] += v;
    d[r + 1] -= v;
}
// 所有操作做完后:
for (int i = 1; i < n; i++) d[i] += d[i - 1];
// 现在 d[0..n-1] 就是最终数组

为什么对:dd 的前缀和是aa。在d[l]d[l] 加vv 会让a[l],a[l+1],…a[l], a[l+1], \dots 全部+v+v;在d[r+1]d[r+1] 减vv 会把a[r+1]a[r+1] 及之后抵消回去。

复杂度:qq 次区间加 →O(q+n)O(q + n) 而不是O(q⋅n)O(q \cdot n)。

典型题:区间覆盖次数

有qq 个区间[li,ri][l_i, r_i],问每个位置被覆盖了多少次。

vector<int> d(n + 2, 0);
for (auto& [l, r] : intervals) { d[l]++; d[r + 1]--; }
for (int i = 1; i <= n; i++) d[i] += d[i - 1];
// d[i] 就是位置 i 的覆盖次数

二维差分

同理,二维差分的前缀和是原数组。

矩形加

给矩形(x1,y1)(x_1,y_1) 到(x2,y2)(x_2,y_2) 全部+v+v:

d[x1][y1]       += v
d[x1][y2+1]     -= v
d[x2+1][y1]     -= v
d[x2+1][y2+1]   += v
void add(int x1, int y1, int x2, int y2, long long v) {
    d[x1][y1]     += v;
    d[x1][y2 + 1] -= v;
    d[x2 + 1][y1] -= v;
    d[x2 + 1][y2 + 1] += v;
}

和二维前缀和的查询公式完全对称(把++ 和−- 对调),因为差分是前缀和的逆运算。

记忆方法:二维容斥的四个角,符号是 + - - +(左上角加,右上左下减,右下角加)。

进阶:带权/高阶前缀和

差分的高阶:多项式区间加

给[l,r][l, r] 加上一个等差数列(如+1,+2,+3,…+1, +2, +3, \dots)。

用二阶差分:一次差分后再差分。

一次差分: d[l] += 1, d[r+1] -= 1        → 区间 +1
若要做 "区间加等差数列",需要维护一阶差分的差分

实际实现:维护差分数组dd,区间加等差数列时:

// 给 [l, r] 加上首项 a、公差 d0 的等差数列
diff[l]     += a;
diff[l + 1] += d0 - a;
diff[r + 1] -= a + (r - l) * d0;
diff[r + 2] -= d0 - (a + (r - l) * d0) ...   // 容易写错

这类题容易写错边界,更稳妥的做法是用线段树 + 懒标记,或者记住"做两次前缀和"的结构。

前缀和的变体

前缀最值

pre[i]=max⁡(a[0..i]),suf[i]=max⁡(a[i..n−1])pre[i] = \max(a[0..i]), \quad suf[i] = \max(a[i..n-1])

vector<int> pre(n), suf(n);
pre[0] = a[0];
for (int i = 1; i < n; i++) pre[i] = max(pre[i-1], a[i]);
suf[n-1] = a[n-1];
for (int i = n-2; i >= 0; i--) suf[i] = max(suf[i+1], a[i]);

典型应用:

  • 接雨水(每个位置能接多少 = min(pre_max, suf_max) - h[i])
  • 除自身以外数组的乘积(前缀积 × 后缀积)
  • 股票买卖(从左到右扫最大收益)

前缀积(模意义下)

vector<long long> pre(n + 1, 1);
for (int i = 1; i <= n; i++) pre[i] = pre[i-1] * a[i-1] % MOD;

// 区间积 query(l, r) 需要逆元:
long long prod = pre[r] * qpow(pre[l-1], MOD-2, MOD) % MOD;

需要模数是质数才能用费马小定理求逆元。或者用前缀积 + 后缀积避开逆元。

前缀异或和

sx[i]=a[0]⊕a[1]⊕⋯⊕a[i]sx[i] = a[0] \oplus a[1] \oplus \cdots \oplus a[i]

性质:xor(l,r)=sx[r]⊕sx[l−1]\text{xor}(l, r) = sx[r] \oplus sx[l-1](因为x⊕x=0x \oplus x = 0)。

应用:子数组异或和为 0 ⟺ 两个前缀异或和相等。

树上前缀和

从根到节点的路径和(或路径上的某种累计量):

// dfs 时累计
void dfs(int u, int p, long long acc) {
    pathSum[u] = acc + val[u];
    for (int v : g[u]) if (v != p) dfs(v, u, pathSum[u]);
}

两点路径上的和:

sum(u,v)=pathSum[u]+pathSum[v]−2⋅pathSum[lca]+val[lca]\text{sum}(u,v) = \text{pathSum}[u] + \text{pathSum}[v] - 2 \cdot \text{pathSum}[\text{lca}] + \text{val}[\text{lca}]

点权版本要用 LCA(见倍增章节)。

与其他数据结构的对比

需求工具单次复杂度
静态区间和前缀和O(1)O(1) 查询,O(n)O(n) 预处理
区间加 + 单点查差分O(1)O(1) 修改
单点加 + 区间和树状数组 / 线段树O(log⁡n)O(\log n)
区间加 + 区间和线段树(懒标记)O(log⁡n)O(\log n)
多次区间加,最后统一查差分O(1)O(1) 修改 +O(n)O(n) 收尾

选型的判断依据:

修改和查询是否交错?
  - 全部修改在前、全部查询在后 → 差分(最快)
  - 交替进行                   → 树状数组 / 线段树

这是最常用的优化:很多线段树题,如果离线处理,用差分就能O(n)O(n) 解决。

典型例题模式

1. 离线区间加 + 最后查询

// q 次操作"给 [l,r] 加 v",最后问每个位置的值
// → 差分,O(q + n)

2. 区间和等于定值

// 前缀和 + 哈希表,O(n)

3. 最大子数组和(Kadane / 前缀和)

// 前缀和视角:max over j of (s[j] - min_{i<j} s[i])
long long best = LLONG_MIN, minPre = 0, s = 0;
for (long long x : a) {
    s += x;
    best = max(best, s - minPre);
    minPre = min(minPre, s);
}

4. 矩阵区域和(多次查询)

// 二维前缀和,O(1) 查询

5. 区间加 + 单点查询(多次交替)

// 差分 + 树状数组:把"区间加"变成差分数组上的"两个单点加"
// 把"单点查"变成差分数组上的"前缀和查询"
// → 树状数组 O(log n)

这就是树状数组维护差分的技巧,兼顾了差分的简洁和动态查询。

常见坑

  • 1-indexed vs 0-indexed 混乱:前缀和建议用 s[n+1],s[0]=0
  • s[r] - s[l-1] 写成 s[r] - s[l]:差一错误,最常见
  • 忘记 long long:前缀和是累加,很容易爆 int(10510^5 个10910^9 的数累加 =101410^{14})
  • 差分数组开太小:d[r+1] 会越界,要开 n+2
  • 二维容斥符号写错:记住 + - - +
  • 哈希表的初始值:cnt[0] = 1 不能忘
  • 差分还原时的范围:只还原到 n-1,d[n] 是哨兵不用管
  • 前缀和用于动态数组:数组会变时前缀和失效,要用树状数组
  • 负数取模:前缀积/和涉及取模时,(x % MOD + MOD) % MOD