累积和与差分

前言

想象你是一个老师，手里有 1000 个学生的成绩。校长问你：“第 100 名到第 200 名的总分是多少？“你扫了一遍，算出来了。然后校长又问：“第 50 名到第 300 名呢？“你又扫了一遍。然后又问”第 1 名到第 500 名呢”……

你烦了：“能不能一次算好，以后直接查？”

这就是前缀和的起源。它的想法朴素而强大：先把所有”从开头到第 $i$ 个”的和算好存在一个数组里，之后任何区间查询只需要查两个数、做一次减法。花 $O(n)$ 预处理，换来每次查询 $O(1)$。

差分是前缀和的”逆操作”。前缀和是”从元素数组算出累加和”，差分就是”从累加和还原出元素数组”。这个逆关系让”区间修改”（给一段区间的每个数都加 $x$）变得极快——两次单点操作就搞定了。

问题的本质

前缀和：用减法代替累加

假如有一列数：$a = [3, 1, 4, 1, 5, 9, 2, 6]$。定义前缀和 $S_i = a_1 + a_2 + \cdots + a_i$：

$i$	0	1	2	3	4	5	6	7	8
$a_i$	—	3	1	4	1	5	9	2	6
$S_i$	0	3	4	8	9	14	23	25	31

问”第 3 到第 6 个数的和”——也就是 $a_3 + a_4 + a_5 + a_6 = 4 + 1 + 5 + 9 = 19$。

用前缀和：$S_6 - S_2 = 23 - 4 = 19$。一次减法搞定。

为什么是对的？$S_6$ 是 $a_1 + a_2 + a_3 + a_4 + a_5 + a_6 = 23$。$S_2$ 是 $a_1 + a_2 = 4$。一减就把 $a_1, a_2$ 消掉了，只剩下 $a_3$ 到 $a_6$。

差分：用加法代替区间修改

反过来想：如果我想把 $a_3$ 到 $a_6$ 全部加 10，朴素做法是循环 4 次给 $a_3, a_4, a_5, a_6$ 各加 10。但如果用差分数组 $d$：

d[3] += 10     ← 从位置 3 开始"加 10"生效
d[7] -= 10     ← 从位置 7 开始"加 10"取消

然后对 $d$ 做一次前缀和，就能还原出修改后的 $a$。不管区间多长，修改操作永远只需两步。

理论 + 代码

一维前缀和

long long a[100010], S[100010];

// 预处理
S[0] = 0;                              // ① 边界：S[0] = 0
for (int i = 1; i <= N; i++)
    S[i] = S[i - 1] + a[i];            // ② 递推

// 查询区间 [l, r] 的和
long long sum = S[r] - S[l - 1];       // ③ 一次减法

• ① 为什么需要 $S[0] = 0$？因为查询 $[1, r]$ 时要用到 $S[l-1] = S[0]$。如果不设 $S[0] = 0$，$S[1] - S[0]$ 里的 $S[0]$ 就没有定义。
• ② 每步只做一次加法，$O(N)$。
• ③ 无论区间多长，查询都是一次减法——$O(1)$。

差分数组

long long d[100010] = {};   // 全部初始化为 0

// 对区间 [l, r] 的所有元素加 x
d[l] += x;                  // ① 从 l 开始，值增加了 x
d[r + 1] -= x;              // ② 从 r+1 开始，增加的效果取消

// 还原
for (int i = 1; i <= N; i++)
    d[i] += d[i - 1];       // ③ 对差分数组做前缀和 = 修改后的原数组

走一遍具体过程：原数组 $a = [0, 0, 0, 0, 0, 0]$（6 个 0），对 $[2, 4]$ 加 10。

步骤 1：d[2] += 10, d[5] -= 10。$d = [0, 0, 10, 0, 0, -10, 0]$。

步骤 2：对 $d$ 做前缀和：

$i$	$d_i$（差分）	$d_i$（前缀和后）= 修改后的 $a_i$
0	0	0
1	0	0
2	10	10
3	0	10
4	0	10
5	-10	0
6	0	0

还原后 $a = [0, 0, 10, 10, 10, 0]$。位置 2、3、4 各加了 10，其他位置不变。✓

为什么管用？d[l] += x 让从 $l$ 开始的所有位置在做前缀和后都多了 $x$。d[r+1] -= x 让从 $r+1$ 开始多的 $x$ 被抵消。所以效果恰好是 $[l, r]$ 加了 $x$。

二维前缀和

二维的情况用容斥原理（后面 02-06 容斥原理 会详细讲）：

$$S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + a[i][j]$$

为什么有减法？因为 $S[i-1][j]$（上方矩形）和 $S[i][j-1]$（左方矩形）都包含了 $S[i-1][j-1]$（左上角）的部分，被加了两次。减掉一次才是正确的。

查询矩形 $(x_1, y_1)$ 到 $(x_2, y_2)$：

$$\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]$$

同样的容斥：减去上面和左边的多余部分，加回被多减的左上角。

前缀思想的推广

前缀和的核心思想是”预处理递推信息，$O(1)$ 查询”。这个思想不局限于”求和”——任何满足结合律的操作都可以用前缀预处理：

操作	前缀递推公式	查询公式
求和	$S[i] = S[i-1] + a[i]$	$\text{sum}(l,r) = S[r] - S[l-1]$
最大值	$M[i] = \max(M[i-1], a[i])$	$\max(l,r)$ 需要其他方法（ST 表，03-07）
左侧最大值	$L[i] = \max(L[i-1], a[i])$	直接查 $L[r]$（前 $r$ 个的最大值）
右侧最大值	$R[i] = \max(R[i+1], a[i])$	直接查 $R[l]$（从 $l$ 到末尾的最大值）

“左侧最大值”和”右侧最大值”在很多题目中很有用。比如：给你一个数组，$Q$ 次查询”去掉区间 $[l,r]$ 后，剩余部分的最大值是多少？“答案就是 $\max(L[l-1], R[r+1])$——左边部分的最大值和右边部分的最大值取较大者。预处理 $O(n)$，查询 $O(1)$。

例题

例题 1：M&A 038 — How Many Guests?（★2）

题目：游乐园「ALGO-RESORT」举办 $N$ 天的活动，第 $i$ 天有 $A_i$ 人到场。有 $Q$ 个询问，每个询问给 $L, R$，求第 $L$ 天到第 $R$ 天的总到场人数。

数据范围：$1 \le N, Q \le 10^5$，$1 \le A_i \le 10000$

—— AtCoder M&A 038

思路：裸的一维前缀和。如果每次询问都循环累加，$O(NQ) = 10^{10}$，TLE。用前缀和预处理 $O(N)$，每次查询 $O(1)$。

代码：

#include <cstdio>
using namespace std;

int main() {
    int N, Q;
    scanf("%d%d", &N, &Q);
    long long A[100010], S[100010];
    S[0] = 0;
    for (int i = 1; i <= N; i++) {
        scanf("%lld", &A[i]);
        S[i] = S[i - 1] + A[i];    // ① 前缀和递推
    }

    for (int q = 0; q < Q; q++) {
        int L, R;
        scanf("%d%d", &L, &R);
        printf("%lld\n", S[R] - S[L - 1]);  // ② 一次减法
    }
}

逐行解析：

• ① S[i] = S[i-1] + A[i]：前缀和递推。$S_i = A_1 + A_2 + \cdots + A_i$。
• ② S[R] - S[L-1]：区间 $[L, R]$ 的和。无论区间多长，查询始终 $O(1)$。

---

例题 2：Tessoku Book — A08 Two Dimensional Sum

题目：给定一个 $H \times W$ 的矩阵，第 $i$ 行第 $j$ 列的值为 $X_{i,j}$。有 $Q$ 个询问，每个询问给 $(A, B, C, D)$，求以 $(A, B)$ 为左上角、$(C, D)$ 为右下角的子矩阵的元素之和。

数据范围：$1 \le H, W \le 1500$，$1 \le Q \le 100000$，$0 \le X_{i,j} \le 9$

—— AtCoder Tessoku Book A08

思路：二维前缀和裸题。每次查询如果扫描子矩阵，$O(HWQ) \approx 3 \times 10^{11}$，绝对 TLE。用二维前缀和，预处理 $O(HW)$，每次查询 $O(1)$。

代码：

#include <cstdio>
using namespace std;

int X[1510][1510];
long long S[1510][1510];

int main() {
    int H, W, Q;
    scanf("%d%d%d", &H, &W, &Q);
    for (int i = 1; i <= H; i++)
        for (int j = 1; j <= W; j++)
            scanf("%d", &X[i][j]);

    // ① 二维前缀和
    for (int i = 1; i <= H; i++)
        for (int j = 1; j <= W; j++)
            S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + X[i][j];

    for (int q = 0; q < Q; q++) {
        int A, B, C, D;
        scanf("%d%d%d%d", &A, &B, &C, &D);
        // ② 容斥查询
        printf("%lld\n", S[C][D] - S[A-1][D] - S[C][B-1] + S[A-1][B-1]);
    }
}

逐行解析：

• ① 二维前缀和递推：$S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + X[i][j]$。减去 $S[i-1][j-1]$ 是因为被 $S[i-1][j]$ 和 $S[i][j-1]$ 各加了一次。
• ② 查询子矩阵 $(A,B)$ 到 $(C,D)$：$S[C][D] - S[A-1][D] - S[C][B-1] + S[A-1][B-1]$。同样容斥：减去上面和左边多出的部分，加回被多减的左上角。

---

例题 3：Tessoku Book — A09 Winter in ALGO Kingdom

题目：ALGO 王国是一个 $H \times W$ 的网格。初始没有积雪。接下来 $N$ 天，第 $t$ 天在以 $(A_t, B_t)$ 为左上角、$(C_t, D_t)$ 为右下角的矩形区域内积雪增加 1cm。输出最终每个格子的积雪量。

数据范围：$1 \le H, W \le 1500$，$1 \le N \le 100000$

—— AtCoder Tessoku Book A09

思路：经典的二维差分。每次对一个矩形区域加 1，朴素做法是 $O(HW)$ 每次操作，$N$ 次共 $O(NHW) \approx 2.25 \times 10^{11}$，TLE。用二维差分，每次操作 $O(1)$（修改差分数组的 4 个位置），最后做一次二维前缀和还原。

二维差分的四个修改点：

d[A][B]     += 1    // 左上角开始生效
d[A][D+1]   -= 1    // 右上角外取消
d[C+1][B]   -= 1    // 左下角外取消
d[C+1][D+1] += 1    // 右下角外补偿

代码：

#include <cstdio>
using namespace std;

int d[1510][1510];

int main() {
    int H, W, N;
    scanf("%d%d%d", &H, &W, &N);

    for (int t = 0; t < N; t++) {
        int A, B, C, D;
        scanf("%d%d%d%d", &A, &B, &C, &D);
        d[A][B]++;           // ① 左上 +1
        d[A][D + 1]--;       // ② 右上外 -1
        d[C + 1][B]--;       // ③ 左下外 -1
        d[C + 1][D + 1]++;   // ④ 右下外 +1（补偿多减）
    }

    // ⑤ 两次前缀和还原
    // 先按行做前缀和
    for (int i = 1; i <= H; i++)
        for (int j = 1; j <= W; j++)
            d[i][j] += d[i][j - 1];
    // 再按列做前缀和
    for (int j = 1; j <= W; j++)
        for (int i = 1; i <= H; i++)
            d[i][j] += d[i - 1][j];

    // ⑥ 输出
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            if (j > 1) printf(" ");
            printf("%d", d[i][j]);
        }
        printf("\n");
    }
}

逐行解析：

• ①②③④ 是二维差分的标准四点修改。把”矩形区域加 1”变成 4 次单点操作。
• ⑤ 还原时做两次一维前缀和：先按行扫，再按列扫。等价于二维前缀和。

走一遍过程：$H=W=5, N=2$，操作 $(1,1,3,3)$ 和 $(2,2,4,4)$。

操作1后差分数组：

d[1][1]=1  d[1][4]=-1
d[4][1]=-1  d[4][4]=1

操作2后差分数组：

d[2][2]+=1  d[2][5]-=1
d[5][2]-=1  d[5][5]+=1

还原后（最终积雪）：

1 1 1 0 0
1 2 2 1 0
1 2 2 1 0
0 1 1 1 0
0 0 0 0 0

和题目样例一致。✓

---

例题 4：T90 010 — Score Sum Queries（★2）

题目：ABC 大学有 $N$ 名一年级学生，学号 $i$ 的学生在 $C_i$ 班（$C_i \in \{1, 2\}$），期末成绩 $P_i$。有 $Q$ 个询问，每个给 $L, R$，求学号 $L$ 到 $R$ 中 1 班学生的总分和 2 班学生的总分。

数据范围：$1 \le N, Q \le 10^5$，$0 \le P_i \le 100$

—— AtCoder Typical 90 010

思路：对每个班级分别维护前缀和。$S_1[i]$ = 前 $i$ 个学生中 1 班的总分，$S_2[i]$ = 前 $i$ 个学生中 2 班的总分。查询时分别做减法。

代码：

#include <cstdio>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    int C[100010], P[100010];
    long long S1[100010] = {}, S2[100010] = {};  // ① 两个前缀和数组

    for (int i = 1; i <= N; i++) {
        scanf("%d%d", &C[i], &P[i]);
        S1[i] = S1[i - 1] + (C[i] == 1 ? P[i] : 0);  // ② 只累加 1 班
        S2[i] = S2[i - 1] + (C[i] == 2 ? P[i] : 0);  // ③ 只累加 2 班
    }

    int Q;
    scanf("%d", &Q);
    while (Q--) {
        int L, R;
        scanf("%d%d", &L, &R);
        printf("%lld %lld\n",
            S1[R] - S1[L - 1],   // ④ 1 班区间和
            S2[R] - S2[L - 1]);   // ⑤ 2 班区间和
    }
}

逐行解析：

• ②③ C[i] == 1 ? P[i] : 0：三目运算符。如果学生 $i$ 在 1 班就加上 $P_i$，否则加 0。这样 $S_1$ 只累计 1 班的分数。
• ④⑤ 对每个前缀和数组分别做区间查询。

这道题的核心技巧是按类别分别维护前缀和。如果类别有 $K$ 种，就需要 $K$ 个前缀和数组。

---

例题 5：Tessoku Book — A10 Resort Hotel

题目：某度假酒店有 $N$ 个房间（1 到 $N$ 号），$i$ 号房是 $A_i$ 人房。接下来 $D$ 天每天有工程，第 $d$ 天不能使用 $L_d$ 到 $R_d$ 号房间。对每一天，求能用的房间中最大能住多少人。

数据范围：$3 \le N \le 100000$，$1 \le D \le 100000$，$1 \le A_i \le 100$，$2 \le L_d \le R_d \le N - 1$

—— AtCoder Tessoku Book A10

思路：去掉区间 $[L, R]$ 后，剩下的部分是 $[1, L-1]$ 和 $[R+1, N]$。要求这两段中的最大值——这正是 00-03 理论部分 讲的”前缀最大值”的应用。

预处理两个数组：

• L[i] = $\max(A_1, A_2, \ldots, A_i)$——从左到右的前缀最大值
• R[i] = $\max(A_i, A_{i+1}, \ldots, A_N)$——从右到左的后缀最大值

查询”去掉 $[L, R]$ 后的最大值”就是 $\max(L[L-1], R[R+1])$。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

int A[100010], L[100010], R[100010];

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
        scanf("%d", &A[i]);

    // ① 前缀最大值
    L[0] = 0;
    for (int i = 1; i <= N; i++)
        L[i] = max(L[i - 1], A[i]);

    // ② 后缀最大值
    R[N + 1] = 0;
    for (int i = N; i >= 1; i--)
        R[i] = max(R[i + 1], A[i]);

    // ③ 回答每个查询
    int D;
    scanf("%d", &D);
    while (D--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", max(L[l - 1], R[r + 1]));  // ④ 左段和右段取最大
    }
}

逐行解析：

• ① L[i] = max(L[i-1], A[i])：前缀最大值递推。$L[i]$ 是前 $i$ 个房间的最大容量。
• ② R[i] = max(R[i+1], A[i])：后缀最大值。从右往左扫，$R[i]$ 是从 $i$ 到 $N$ 的最大容量。
• ④ 去掉 $[l, r]$ 后，左边最大是 $L[l-1]$，右边最大是 $R[r+1]$，取较大者就是答案。

走一遍过程：$N = 7$，$A = [1, 2, 5, 5, 2, 3, 1]$。

$i$	0	1	2	3	4	5	6	7	8
$A_i$	—	1	2	5	5	2	3	1	—
$L[i]$	0	1	2	5	5	5	5	5	—
$R[i]$	—	5	5	5	5	3	3	1	0

查询 $L=3, R=5$：$\max(L[2], R[6]) = \max(2, 3) = 3$。✓ 查询 $L=4, R=6$：$\max(L[3], R[7]) = \max(5, 1) = 5$。✓

这道题完美展示了前缀思想的推广——不只是”求和”，“求最大值”也可以用同样的预处理思路。

参考文献

教材讲解 — 競技プログラミングの鉄則 第 2 章

• 2.1 B06 Lottery（累积和基础 解说）
• 2.2 B07 Convenience Store 2（差分+累积和 解说）

基础练习 — アルゴリズムと数学 演習問題集

• 038 How Many Guests?（前缀和区间查询）【例题】
• 005 Modulo 100（累加取模）
• 039 Snowy Days（差分数组）
• 041 Convenience Store 2（imos法）
• 067 Cross Sum（行和+列和预计算）

系统练习 — 競技プログラミングの鉄則

• A08 Two Dimensional Sum（二维前缀和）【例题】
• A09 Winter in ALGO Kingdom（二维差分）【例题】
• A10 Resort Hotel（前缀/后缀最大值）【例题】
• A06 How Many Guests?（前缀和，同M&A 038）
• A07 Event Attendance（差分+前缀和）
• B08 Counting Points（二维前缀和查询）
• B09 Papers（二维差分求覆盖面积）

实战练习 — 競プロ典型 90 問

• 010 Score Sum Queries（★2，分类前缀和）【例题】
• 064 Uplift（★3，差分维护不便度）

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化