尧图网页设计 
CSP-J/S 前缀和讲义前缀和是信息学竞赛中最基础、最常用的预处理技巧之一在 CSP-J/S 的初赛和复赛中都有广泛应用。它可以将“多次查询一个静态区间/子矩阵的和”这类问题的时间复杂度从 O(nq)O(nq) 优化到 O(nq)O(nq)并且在差分、哈希、动态规划优化等问题中扮演重要角色。本讲义面向 CSP-J/S 备考学生内容覆盖一维前缀和、二维前缀和、差分数组、前缀和的常见变体以及大量经典例题力求详细、系统、可操作。目录前缀和的概念与引入一维前缀和2.1 定义与递推公式2.2 查询区间和2.3 代码实现2.4 下标从 0 开始的注意事项2.5 时间复杂度与数据范围二维前缀和3.1 定义与递推公式3.2 查询子矩阵和3.3 代码实现3.4 图形化理解与示例前缀和与差分4.1 一维差分4.2 二维差分4.3 差分与前缀和的关系前缀和与子段和问题5.1 子段和与两个前缀和的差5.2 最大子段和5.3 和为 K 的子数组5.4 和为 K 的倍数的子数组前缀和的变体6.1 前缀异或和6.2 前缀乘积6.3 前缀最大值/最小值6.4 高维前缀和简介经典例题精讲7.1 一维前缀和模板题7.2 二维前缀和模板题7.3 最大加权矩形7.4 领地选择7.5 地毯7.6 光骓者的荣耀7.7 和为 K 的子数组7.8 异或和为 0 的子数组易错点与代码技巧总结练习题推荐1. 前缀和的概念与引入考虑这样一个问题给定一个长度为 nn 的整数数组 aa有 qq 次询问每次询问一个区间 [l,r][l,r] 内所有元素的和。如果每次询问都从 a[l]a[l] 加到 a[r]a[r]最坏情况下每次需要 O(n)O(n) 的时间总时间复杂度为 O(nq)O(nq)。当 n,qn,q 都达到 105105 级别时操作次数可能达到 10101010在 C 中会超时。前缀和的核心思想是提前预处理出从数组开头到每个位置的累加和之后任意一个区间的和都可以通过两个前缀和相减快速得到。例如texta [3, 1, 4, 1, 5, 9, 2, 6] 前缀和 s [0, 3, 4, 8, 9, 14, 23, 25, 31]如果要查询区间 [3,6][3,6] 的和即 a[3]a[4]a[5]a[6]415919a[3]a[4]a[5]a[6]415919可以直接计算 s[6]−s[2]23−419s[6]−s[2]23−419。这就是前缀和的基本思想用空间换时间把重复计算转化为一次预处理和若干次快速查询。2. 一维前缀和2.1 定义与递推公式设原数组为 a[1],a[2],…,a[n]a[1],a[2],…,a[n]定义前缀和数组 sss[i]∑j1ia[j]a[1]a[2]⋯a[i]s[i]j1∑ia[j]a[1]a[2]⋯a[i]特别地定义 s[0]0s[0]0表示空区间的前缀和。前缀和数组可以通过递推得到s[i]s[i−1]a[i]s[i]s[i−1]a[i]这个公式的含义是前 ii 个元素的和等于前 i−1i−1 个元素的和再加上第 ii 个元素。2.2 查询区间和对于任意区间 [l,r][l,r]其中 1≤l≤r≤n1≤l≤r≤n其元素和为∑jlra[j]s[r]−s[l−1]jl∑ra[j]s[r]−s[l−1]理解前 rr 个元素的和减去前 l−1l−1 个元素的和剩下的就是第 ll 到第 rr 个元素的和。由于 s[0]0s[0]0当 l1l1 时公式依然成立s[r]−s[0]s[r]s[r]−s[0]s[r]这就是为什么我们通常把前缀和数组下标从 1 开始并设置 s[0]0s[0]0这样可以避免对左端点为 1 的情况进行特判。2.3 代码实现cpp#include bits/stdc.h using namespace std; const int MAXN 1e5 5; int n, q; long long a[MAXN], s[MAXN]; void build_prefix_sum() { s[0] 0; for (int i 1; i n; i) { s[i] s[i - 1] a[i]; } } long long query_sum(int l, int r) { return s[r] - s[l - 1]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n q; for (int i 1; i n; i) { cin a[i]; } build_prefix_sum(); while (q--) { int l, r; cin l r; cout query_sum(l, r) \n; } return 0; }说明数组下标从 1 开始方便处理边界。使用long long防止累加和溢出。预处理一次 O(n)O(n)每次查询 O(1)O(1)。如果题目输入输出量大建议使用scanf/printf或关闭同步的cin/cout。2.4 下标从 0 开始的注意事项有些题目给出的数组下标习惯从 0 开始。此时可以将前缀和数组定义为 s[i1]s[i1] 表示前 i1i1 个元素的和即cpp// a[0..n-1] // s[i] 表示 a[0] ... a[i-1] vectorlong long s(n 1, 0); for (int i 0; i n; i) { s[i 1] s[i] a[i]; } // 查询 [l, r] 闭区间0-based long long sum s[r 1] - s[l];或者仍然定义前缀和数组与原数组等长但需要处理左端点为 0 的情况。推荐统一使用“长度加一”的前缀和数组下标从 1 开始。2.5 时间复杂度与数据范围预处理时间复杂度O(n)O(n)单次查询时间复杂度O(1)O(1)总时间复杂度O(nq)O(nq)空间复杂度O(n)O(n)数据范围注意点如果数组元素值较大累加和可能超过int的范围。例如 n105n105每个元素 105105总和可达 10101010需要使用long long。如果前缀和用于哈希表注意键的范围。3. 二维前缀和3.1 定义与递推公式二维前缀和用于处理矩阵中的子矩阵求和问题。设原矩阵为 a[i][j]a[i][j]其中 1≤i≤n1≤i≤n1≤j≤m1≤j≤m。定义二维前缀和 s[i][j]s[i][j] 表示以 (1,1)(1,1) 为左上角以 (i,j)(i,j) 为右下角的子矩阵中所有元素的和s[i][j]∑x1i∑y1ja[x][y]s[i][j]x1∑iy1∑ja[x][y]递推公式s[i][j]s[i−1][j]s[i][j−1]−s[i−1][j−1]a[i][j]s[i][j]s[i−1][j]s[i][j−1]−s[i−1][j−1]a[i][j]推导理解要计算 s[i][j]s[i][j]可以先加上上方矩形 s[i−1][j]s[i−1][j]即前 i−1i−1 行、前 jj 列的和再加上左方矩形 s[i][j−1]s[i][j−1]即前 ii 行、前 j−1j−1 列的和。但这样左上角的矩形 s[i−1][j−1]s[i−1][j−1] 被重复加了一次所以减去。最后加上当前元素 a[i][j]a[i][j]。3.2 查询子矩阵和如果要查询以 (x1,y1)(x1,y1) 为左上角、(x2,y2)(x2,y2) 为右下角的子矩阵和其中 1≤x1≤x2≤n1≤x1≤x2≤n1≤y1≤y2≤m1≤y1≤y2≤m公式为sums[x2][y2]−s[x1−1][y2]−s[x2][y1−1]s[x1−1][y1−1]sums[x2][y2]−s[x1−1][y2]−s[x2][y1−1]s[x1−1][y1−1]推导理解从整个大矩形 s[x2][y2]s[x2][y2] 中减去上方多余部分 s[x1−1][y2]s[x1−1][y2]第 11 行到第 x1−1x1−1 行第 11 列到第 y2y2 列再减去左方多余部分 s[x2][y1−1]s[x2][y1−1]第 11 行到第 x2x2 行第 11 列到第 y1−1y1−1 列。但左上角的小矩形 s[x1−1][y1−1]s[x1−1][y1−1] 被重复减了两次所以再加回来。3.3 代码实现cpp#include bits/stdc.h using namespace std; const int MAXN 1005; const int MAXM 1005; int n, m, q; long long a[MAXN][MAXM]; long long s[MAXN][MAXM]; void build_prefix_sum_2d() { for (int i 1; i n; i) { for (int j 1; j m; j) { s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] a[i][j]; } } } long long query_sum_2d(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]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m q; for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; } } build_prefix_sum_2d(); while (q--) { int x1, y1, x2, y2; cin x1 y1 x2 y2; cout query_sum_2d(x1, y1, x2, y2) \n; } return 0; }3.4 图形化理解与示例假设有一个 3×33×3 的矩阵texta: 1 2 3 4 5 6 7 8 9构建二维前缀和计算 s[1][1]s[1][1]texts[1][1] s[0][1] s[1][0] - s[0][0] a[1][1] 0 0 - 0 1 1计算 s[1][2]s[1][2]texts[1][2] s[0][2] s[1][1] - s[0][1] a[1][2] 0 1 - 0 2 3依次计算最终前缀和矩阵为texts: 1 3 6 5 12 21 12 27 45查询子矩阵 (2,2)(2,2) 到 (3,3)(3,3)textsum s[3][3] - s[1][3] - s[3][1] s[1][1] 45 - 6 - 12 1 28验证a[2][2]a[2][3]a[3][2]a[3][3]568928a[2][2]a[2][3]a[3][2]a[3][3]568928正确。二维前缀和的时间复杂度预处理 O(nm)O(nm)单次查询 O(1)O(1)总 O(nmq)O(nmq)。空间复杂度 O(nm)O(nm)。4. 前缀和与差分差分是前缀和的逆运算两者经常结合使用。前缀和解决“静态区间查询”差分解决“动态区间修改后一次查询”的问题。4.1 一维差分问题给定长度为 nn 的数组 aa初始全为 0 或给定值有 qq 次操作每次操作将区间 [l,r][l,r] 中每个元素加上 xx。最后输出修改后的数组。如果直接每次暴力修改时间复杂度 O(nq)O(nq)。使用差分可以做到 O(nq)O(nq)。差分数组定义设原数组为 aa定义差分数组 ddd[i]a[i]−a[i−1]d[i]a[i]−a[i−1]其中 a[0]0a[0]0。由差分数组可以通过前缀和还原原数组a[i]d[1]d[2]⋯d[i]a[i]d[1]d[2]⋯d[i]这正是前缀和的递推。区间修改操作要将区间 [l,r][l,r] 中所有元素加上 xx只需d[l]xd[l]xd[r1]−xd[r1]−x当对 dd 做前缀和时从 ll 开始每个位置会累加上 xx直到 r1r1 处减去 xx之后的位置不再受影响。代码cpp#include bits/stdc.h using namespace std; const int MAXN 1e5 5; int n, q; long long a[MAXN], d[MAXN]; int main() { cin n q; for (int i 1; i n; i) { cin a[i]; d[i] a[i] - a[i-1]; // 构建差分数组 } while (q--) { int l, r, x; cin l r x; d[l] x; if (r 1 n) d[r 1] - x; // 注意越界 } // 对差分数组求前缀和还原修改后的数组 for (int i 1; i n; i) { a[i] a[i-1] d[i]; cout a[i] ; } cout \n; return 0; }4.2 二维差分二维差分用于处理“对多个子矩阵进行加法操作最后输出整个矩阵”的问题。定义设原矩阵为 aa二维差分矩阵为 dd。它们满足a[i][j]∑x1i∑y1jd[x][y]a[i][j]x1∑iy1∑jd[x][y]即 aa 是 dd 的二维前缀和。构建方法若原矩阵 aa 已知可以通过以下方式构建 dd相当于对一个初始全 0 的矩阵对每个 1×11×1 的子矩阵加上 a[i][j]a[i][j]d[i][j]a[i][j]−a[i−1][j]−a[i][j−1]a[i−1][j−1]d[i][j]a[i][j]−a[i−1][j]−a[i][j−1]a[i−1][j−1]子矩阵修改操作要对以 (x1,y1)(x1,y1) 为左上角、(x2,y2)(x2,y2) 为右下角的子矩阵中每个元素加上 xx执行d[x1][y1]xd[x1][y1]xd[x21][y1]−xd[x21][y1]−xd[x1][y21]−xd[x1][y21]−xd[x21][y21]xd[x21][y21]x最后对 dd 做二维前缀和即可得到修改后的矩阵。代码框架cppint n, m, q; long long d[MAXN][MAXM]; void add(int x1, int y1, int x2, int y2, int x) { d[x1][y1] x; if (x2 1 n) d[x2 1][y1] - x; if (y2 1 m) d[x1][y2 1] - x; if (x2 1 n y2 1 m) d[x2 1][y2 1] x; } // 最后还原 for (int i 1; i n; i) { for (int j 1; j m; j) { d[i][j] d[i-1][j] d[i][j-1] - d[i-1][j-1]; // 此时 d[i][j] 就是修改后的 a[i][j] } }4.3 差分与前缀和的关系前缀和原数组 → 前缀和数组用于快速查询区间和。差分原数组 → 差分数组用于快速进行区间修改。两者互为逆运算差分数组的前缀和就是原数组前缀和数组的差分就是原数组。很多题目会结合两者先利用差分进行多次区间修改再利用前缀和还原或查询。5. 前缀和与子段和问题任意一个子段 [l,r][l,r] 的和都可以表示为两个前缀和的差∑ilra[i]s[r]−s[l−1]il∑ra[i]s[r]−s[l−1]这个性质非常强大许多子段和问题都可以转化为对前缀和数组的分析。5.1 子段和与两个前缀和的差对于固定的右端点 rr子段 [l,r][l,r] 的和只取决于左端点 llsums[r]−s[l−1]sums[r]−s[l−1]其中 l≤rl≤r所以 l−1l−1 的范围是 00 到 r−1r−1。因此如果我们想要最大/最小/满足某种条件的子段和可以枚举右端点 rr然后在 s[0..r−1]s[0..r−1] 中寻找合适的前缀和值。5.2 最大子段和问题给定一个长度为 nn 的整数数组可能包含负数求它的一个连续子段使得子段和最大。前缀和做法枚举右端点 rr子段和为 s[r]−s[l−1]s[r]−s[l−1]。要使其最大就需要在 l≤rl≤r 的前提下让 s[l−1]s[l−1] 尽可能小。因此可以维护一个变量min_pre表示已经遍历过的前缀和的最小值。对于每个 rr最大子段和候选为s[r]−min0≤krs[k]s[r]−0≤krmins[k]同时更新答案并更新min_pre。代码cpp#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorlong long a(n 1), s(n 1); for (int i 1; i n; i) { cin a[i]; s[i] s[i-1] a[i]; } long long min_pre 0; // s[0] 0 long long ans LLONG_MIN; for (int i 1; i n; i) { ans max(ans, s[i] - min_pre); min_pre min(min_pre, s[i]); } cout ans \n; return 0; }复杂度O(n)O(n)与经典的 Kadane 算法相同但这是从前缀和角度理解的。5.3 和为 K 的子数组问题给定一个整数数组可能有负数求连续子数组和为 kk 的个数。暴力做法是枚举所有子数组时间复杂度 O(n2)O(n2)。如果 nn 达到 105105会超时。前缀和 哈希表优化对于子数组 [l,r][l,r]和为 kk 等价于s[r]−s[l−1]ks[r]−s[l−1]k即s[l−1]s[r]−ks[l−1]s[r]−k我们可以从左到右遍历右端点 rr用一个哈希表统计已经出现过的前缀和值及其出现次数。对于当前右端点 rr我们需要知道有多少个左端点 l−1l−1 满足 s[l−1]s[r]−ks[l−1]s[r]−k也就是哈希表中键为 s[r]−ks[r]−k 的值。遍历前初始化哈希表cnt[0] 1因为空前缀和 s[0]0s[0]0 是一个合法的左端点。代码cpp#include bits/stdc.h using namespace std; int main() { int n, k; cin n k; vectorint a(n); for (int i 0; i n; i) cin a[i]; unordered_maplong long, int cnt; cnt[0] 1; // 空前缀 long long s 0; long long ans 0; for (int i 0; i n; i) { s a[i]; // 需要 s - k 出现了多少次 if (cnt.count(s - k)) { ans cnt[s - k]; } cnt[s]; } cout ans \n; return 0; }注意如果数组中元素可能很大前缀和用long long。unordered_map在极端情况下可能被卡到 O(n2)O(n2)若题目卡常可以使用map或手写哈希。该算法时间复杂度 O(n)O(n)空间复杂度 O(n)O(n)。5.4 和为 K 的倍数的子数组问题求连续子数组的和能被 kk 整除的个数。子数组和为 kk 的倍数即(s[r]−s[l−1])%k0(s[r]−s[l−1])%k0等价于s[r]%ks[l−1]%ks[r]%ks[l−1]%k因此只需要统计每个余数出现的前缀和个数。对于当前前缀和 s[i]s[i]它与之前所有同余的前缀和都能组成一个满足条件的子数组。注意负数取模在 C 中可能得到负余数可以统一转为非负((s%k)k)%k((s%k)k)%k代码cpp#include bits/stdc.h using namespace std; int main() { int n, k; cin n k; vectorint a(n); for (int i 0; i n; i) cin a[i]; vectorint cnt(k, 0); cnt[0] 1; long long s 0; long long ans 0; for (int i 0; i n; i) { s a[i]; int mod ((s % k) k) % k; ans cnt[mod]; cnt[mod]; } cout ans \n; return 0; }6. 前缀和的变体前缀和的思想不仅限于加法还可以推广到其他满足结合律且存在逆运算的操作。6.1 前缀异或和异或运算满足结合律和交换律且每个元素自己的逆元就是它本身因为 x⊕x0x⊕x0。定义前缀异或和x[i]a[1]⊕a[2]⊕⋯⊕a[i]x[i]a[1]⊕a[2]⊕⋯⊕a[i]递推x[i]x[i−1]⊕a[i]x[i]x[i−1]⊕a[i]区间 [l,r][l,r] 的异或和a[l]⊕a[l1]⊕⋯⊕a[r]x[r]⊕x[l−1]a[l]⊕a[l1]⊕⋯⊕a[r]x[r]⊕x[l−1]应用示例求有多少个子数组的异或和为 0。因为异或和为 0 等价于两个前缀异或和相等所以可以用哈希表统计相同前缀异或值出现的次数。cppunordered_mapint, int cnt; cnt[0] 1; int cur 0; long long ans 0; for (int i 0; i n; i) { cur ^ a[i]; ans cnt[cur]; cnt[cur]; }6.2 前缀乘积定义前缀乘积p[i]a[1]×a[2]×⋯×a[i]p[i]a[1]×a[2]×⋯×a[i]如果数组元素都不是 0并且我们在模一个质数的环境下可以使用乘法逆元来求区间乘积∏jlra[j]p[r]×inv(p[l−1])(modM)jl∏ra[j]p[r]×inv(p[l−1])(modM)但如果数组中有 0则不能直接使用逆元。此时需要特殊处理 0 的位置或者使用线段树等数据结构。6.3 前缀最大值/最小值定义前缀最大值preMax[i]max(preMax[i−1],a[i])preMax[i]max(preMax[i−1],a[i])前缀最小值类似。前缀最值可以快速查询“从头到某个位置的最大/最小值”但不能像前缀和那样通过差值来获得区间最值。区间最值通常使用 ST 表、线段树等。前缀最值在动态规划优化中很常见例如维护最小前缀和来求最大子段和。6.4 高维前缀和简介高维前缀和SOS DP子集动态规划是对多维数组进行前缀和常用于处理子集和问题。例如给定 2n2n 个值 f[mask]f[mask]求对于每个 maskmask其所有子集的 ff 值之和。具体做法是按每个二进制位进行 DPcppfor (int i 0; i n; i) { for (int mask 0; mask (1 n); mask) { if (mask (1 i)) { f[mask] f[mask ^ (1 i)]; } } }该算法时间复杂度 O(n⋅2n)O(n⋅2n)。虽然 CSP-J 较少涉及但在 CSP-S 中可能会遇到。7. 经典例题精讲7.1 一维前缀和模板题题目描述给定 nn 个数qq 次询问每次询问一个区间 [l,r][l,r] 的和。输入格式第一行两个整数 n,qn,q。第二行 nn 个整数。接下来 qq 行每行两个整数 l,rl,r。输出格式对于每次询问输出区间和。数据范围1≤n,q≤1051≤n,q≤105元素绝对值不超过 105105。分析直接使用一维前缀和模板即可。代码cpp#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin n q; vectorlong long s(n 1, 0); for (int i 1; i n; i) { int x; cin x; s[i] s[i-1] x; } while (q--) { int l, r; cin l r; cout s[r] - s[l-1] \n; } return 0; }7.2 二维前缀和模板题题目描述给定一个 n×mn×m 的矩阵qq 次询问每次询问一个子矩阵的和。输入格式第一行三个整数 n,m,qn,m,q。接下来 nn 行每行 mm 个整数。接下来 qq 行每行四个整数 x1,y1,x2,y2x1,y1,x2,y2。输出格式对于每次询问输出子矩阵和。分析使用二维前缀和模板。代码cpp#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin n m q; vectorvectorlong long s(n 1, vectorlong long(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { int x; cin x; s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] x; } } while (q--) { int x1, y1, x2, y2; cin x1 y1 x2 y2; long long ans s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1]; cout ans \n; } return 0; }7.3 最大加权矩形题目来源洛谷 P1719 最大加权矩形也可作为最大子段和的二维扩展题目描述给定一个 n×nn×n 的矩阵求一个子矩阵使得子矩阵内所有元素的和最大。数据范围1≤n≤1201≤n≤120矩阵元素可能为负数。分析如果直接枚举所有子矩阵子矩阵有 O(n4)O(n4) 个不可行。但可以枚举矩阵的上下边界将二维问题压缩成一维。具体做法枚举上边界top和下边界bottop≤bottop≤bot。将top到bot行之间的每一列的元素相加得到一个一维数组colSum[j]表示第j列在当前上下边界之间的元素和。对这个一维数组求最大子段和。所有上下边界组合的最大子段和的最大值即为答案。如果直接每次计算colSum需要 O(n)O(n)总复杂度 O(n3)O(n3)因为上下边界 O(n2)O(n2)每次求最大子段和 O(n)O(n)计算列和也需要 O(n)O(n) 但可以优化。当 n≤120n≤120 时O(n3)O(n3) 可行。优化计算列和可以用一维前缀和维护每列的前缀和这样对于固定的上下边界每列的区间和可以 O(1)O(1) 得到。代码cpp#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorvectorint a(n 1, vectorint(n 1)); vectorvectorlong long colPrefix(n 1, vectorlong long(n 1, 0)); for (int i 1; i n; i) { for (int j 1; j n; j) { cin a[i][j]; // 每列的前缀和方便快速求 [top,bot] 行第 j 列的和 colPrefix[i][j] colPrefix[i-1][j] a[i][j]; } } long long ans LLONG_MIN; for (int top 1; top n; top) { for (int bot top; bot n; bot) { // 压缩成一维数组 vectorlong long colSum(n 1, 0); for (int j 1; j n; j) { colSum[j] colPrefix[bot][j] - colPrefix[top-1][j]; } // 求一维最大子段和 long long cur 0; long long maxSum LLONG_MIN; for (int j 1; j n; j) { cur max(colSum[j], cur colSum[j]); maxSum max(maxSum, cur); } ans max(ans, maxSum); } } cout ans \n; return 0; }复杂度O(n3)O(n3)对于 n120n120 足够。7.4 领地选择题目来源洛谷 P2004 领地选择题目描述给定一个 n×mn×m 的矩阵要求选择一个 c×cc×c 的正方形区域使得区域内元素和最大。输出正方形左上角的坐标。分析枚举所有可能的正方形左上角 (i,j)(i,j)利用二维前缀和 O(1)O(1) 计算每个 c×cc×c 正方形的和取最大值。正方形右下角为 (ic−1,jc−1)(ic−1,jc−1)需要保证不越界。代码cpp#include bits/stdc.h using namespace std; int main() { int n, m, c; cin n m c; vectorvectorlong long s(n 1, vectorlong long(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { int x; cin x; s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] x; } } long long best LLONG_MIN; int ansX 1, ansY 1; for (int i 1; i c - 1 n; i) { for (int j 1; j c - 1 m; j) { int x2 i c - 1; int y2 j c - 1; long long sum s[x2][y2] - s[i-1][y2] - s[x2][j-1] s[i-1][j-1]; if (sum best) { best sum; ansX i; ansY j; } } } cout ansX ansY \n; return 0; }7.5 地毯题目来源洛谷 P3397 地毯题目描述在 n×nn×n 的矩阵上铺 mm 块地毯每块地毯覆盖一个子矩阵求最后每个位置被多少块地毯覆盖。数据范围n,m≤1000n,m≤1000。分析这是二维差分的经典应用。对每块地毯覆盖的子矩阵执行二维差分加法操作最后对差分矩阵做二维前缀和即可得到每个位置的覆盖数。代码cpp#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorint d(n 2, vectorint(n 2, 0)); for (int k 0; k m; k) { int x1, y1, x2, y2; cin x1 y1 x2 y2; d[x1][y1] 1; d[x2 1][y1] - 1; d[x1][y2 1] - 1; d[x2 1][y2 1] 1; } // 二维前缀和还原 for (int i 1; i n; i) { for (int j 1; j n; j) { d[i][j] d[i-1][j] d[i][j-1] - d[i-1][j-1]; cout d[i][j] ; } cout \n; } return 0; }7.6 光骓者的荣耀题目来源洛谷 P5638 光骓者的荣耀题目描述有一条长度为 nn 的路路上有 n−1n−1 个传送点第 ii 个传送点可以将人从 ii 传到 ikik。给定相邻站点之间的耗时求从 1 到 nn 的最短时间允许使用一次传送或者不使用。分析该题可以转化为求一段连续长度为 kk 的区间和的最大值然后用总路程减去这个最大值因为传送可以跳过这段路程。先计算出相邻站点之间的时间数组然后求前缀和枚举长度为 kk 的区间求其和的最大值。答案 总时间 - 最大区间和。代码cpp#include bits/stdc.h using namespace std; int main() { int n, k; cin n k; vectorlong long a(n); // a[1..n-1] 表示从 i 到 i1 的时间 vectorlong long s(n 1, 0); for (int i 1; i n - 1; i) { cin a[i]; s[i] s[i-1] a[i]; } long long total s[n-1]; long long maxSkip 0; for (int i 1; i k - 1 n - 1; i) { long long seg s[i k - 1] - s[i - 1]; maxSkip max(maxSkip, seg); } cout total - maxSkip \n; return 0; }7.7 和为 K 的子数组题目描述给定一个整数数组和一个整数 kk求该数组中和为 kk 的连续子数组的个数。分析已在 5.3 节详细讲解使用前缀和 哈希表。代码cpp#include bits/stdc.h using namespace std; int main() { int n, k; cin n k; vectorint a(n); for (int i 0; i n; i) cin a[i]; unordered_maplong long, int cnt; cnt[0] 1; long long s 0; long long ans 0; for (int i 0; i n; i) { s a[i]; if (cnt.count(s - k)) { ans cnt[s - k]; } cnt[s]; } cout ans \n; return 0; }7.8 异或和为 0 的子数组题目描述给定一个整数数组求异或和为 0 的连续子数组的个数。分析一个子数组的异或和为 0 等价于其左右两端的前缀异或和相等。因此统计相同前缀异或值的出现次数。代码cpp#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; unordered_mapint, int cnt; cnt[0] 1; int cur 0; long long ans 0; for (int i 0; i n; i) { cur ^ a[i]; ans cnt[cur]; cnt[cur]; } cout ans \n; return 0; }8. 易错点与代码技巧下标从 1 开始使用前缀和时推荐将数组下标从 1 开始并设置 s[0]0s[0]0。这样可以避免左端点为 1 时的特判代码更简洁。数据类型前缀和累加后可能超过int范围务必使用long long。尤其是二维前缀和元素数量可能达到 106106累加和很容易超过 231−1231−1。二维前缀和边界查询子矩阵时公式中的 x1−1x1−1、y1−1y1−1 可能为 0这是合法的因为 s[0][j]0s[0][j]0、s[i][0]0s[i][0]0。但必须确保前缀和数组的第 0 行和第 0 列初始化为 0。差分数组越界一维差分中d[r1]d[r1] 可能越界需要判断 r1≤nr1≤n。二维差分中需要判断 x21≤nx21≤n 和 y21≤my21≤m。哈希表性能C 的unordered_map在最坏情况下可能被构造的数据卡成 O(n)O(n) 单次操作导致整体 O(n2)O(n2)。如果题目对性能要求高可以使用map稳定 O(logn)O(logn)或手写哈希表。负数取模在求“和为 K 的倍数”时C 中负数取模可能得到负数需要转换为非负余数((s % k) k) % k。输入输出优化当 n,qn,q 达到 106106 级别时使用ios::sync_with_stdio(false); cin.tie(nullptr);或直接使用scanf/printf避免 I/O 成为瓶颈。前缀和的逆运算前缀和和差分是互逆的。如果题目中既有区间修改又有区间查询单纯的前缀和无法胜任需要树状数组或线段树。注意区分题目是静态查询还是动态修改。子段和问题任意子段和都可以表示为两个前缀和之差因此很多子段和问题可以转化为在前缀和数组中寻找满足某种关系的两个位置常常结合哈希表、双指针、二分等技巧。空间优化对于一维前缀和有时可以直接在原数组上累加节省空间。但要注意保留原数组以备后续使用。9. 总结前缀和是一种非常基础但极其重要的预处理技巧它将“区间查询”从 O(n)O(n) 降到 O(1)O(1)在静态数组场景下具有巨大优势。本讲义重点内容回顾一维前缀和s[i]s[i−1]a[i]s[i]s[i−1]a[i]查询 [l,r][l,r] 为 s[r]−s[l−1]s[r]−s[l−1]。二维前缀和递推公式 s[i][j]s[i−1][j]s[i][j−1]−s[i−1][j−1]a[i][j]s[i][j]s[i−1][j]s[i][j−1]−s[i−1][j−1]a[i][j]查询子矩阵和公式类似。差分前缀和的逆运算用于快速进行区间修改。子段和问题利用 s[r]−s[l−1]s[r]−s[l−1]结合最小前缀、哈希表等方法解决最大子段和、和为 K 的子数组等问题。变体前缀异或和、前缀乘积、前缀最值等。前缀和不仅在基础题中直接出现还常常作为复杂算法的预处理步骤。例如在动态规划中前缀和可以用于快速计算状态转移中的区间和在二维问题中二维前缀和可以快速判断子矩阵是否满足条件在字符串问题中前缀和可以用于快速计算区间内字符出现的次数等。掌握前缀和并能灵活运用其变形和组合是 CSP-J/S 复赛中拿到基础分的关键。10. 练习题推荐以下题目适合练习前缀和与差分难度逐渐递增洛谷 P8218 【深进1.例1】求区间和一维前缀和模板。洛谷 P1115 最大子段和前缀和 最小前缀。洛谷 P2004 领地选择二维前缀和枚举正方形。洛谷 P1719 最大加权矩形二维前缀和 压缩成一维最大子段和。洛谷 P3397 地毯二维差分模板。洛谷 P5638 光骓者的荣耀一维前缀和求最大区间和。洛谷 P3131 [USACO16JAN] Subsequences Summing to Sevens S前缀和 余数统计。洛谷 P2697 宝石串前缀和差值统计。洛谷 P1387 最大正方形二维前缀和 二分或枚举边长。洛谷 P2280 [HNOI2003] 激光炸弹二维前缀和注意坐标范围。LeetCode 560 和为 K 的子数组前缀和 哈希表。LeetCode 974 和可被 K 整除的子数组前缀和 余数统计。AcWing 795 前缀和一维模板。AcWing 796 子矩阵的和二维模板。AcWing 797 差分一维差分模板。AcWing 798 差分矩阵二维差分模板。通过大量练习可以熟练掌握前缀和的构建、查询以及与其他算法结合使用的技巧为 CSP-J/S 的复赛打下坚实基础。 CSP-J/S 前缀和讲义
CSP-J/S 前缀和讲义前缀和是信息学竞赛中最基础、最常用的预处理技巧之一在 CSP-J/S 的初赛和复赛中都有广泛应用。它可以将“多次查询一个静态区间/子矩阵的和”这类问题的时间复杂度从 O(nq)O(nq) 优化到 O(nq)O(nq)并且在差分、哈希、动态规划优化等问题中扮演重要角色。本讲义面向 CSP-J/S 备考学生内容覆盖一维前缀和、二维前缀和、差分数组、前缀和的常见变体以及大量经典例题力求详细、系统、可操作。目录前缀和的概念与引入一维前缀和2.1 定义与递推公式2.2 查询区间和2.3 代码实现2.4 下标从 0 开始的注意事项2.5 时间复杂度与数据范围二维前缀和3.1 定义与递推公式3.2 查询子矩阵和3.3 代码实现3.4 图形化理解与示例前缀和与差分4.1 一维差分4.2 二维差分4.3 差分与前缀和的关系前缀和与子段和问题5.1 子段和与两个前缀和的差5.2 最大子段和5.3 和为 K 的子数组5.4 和为 K 的倍数的子数组前缀和的变体6.1 前缀异或和6.2 前缀乘积6.3 前缀最大值/最小值6.4 高维前缀和简介经典例题精讲7.1 一维前缀和模板题7.2 二维前缀和模板题7.3 最大加权矩形7.4 领地选择7.5 地毯7.6 光骓者的荣耀7.7 和为 K 的子数组7.8 异或和为 0 的子数组易错点与代码技巧总结练习题推荐1. 前缀和的概念与引入考虑这样一个问题给定一个长度为 nn 的整数数组 aa有 qq 次询问每次询问一个区间 [l,r][l,r] 内所有元素的和。如果每次询问都从 a[l]a[l] 加到 a[r]a[r]最坏情况下每次需要 O(n)O(n) 的时间总时间复杂度为 O(nq)O(nq)。当 n,qn,q 都达到 105105 级别时操作次数可能达到 10101010在 C 中会超时。前缀和的核心思想是提前预处理出从数组开头到每个位置的累加和之后任意一个区间的和都可以通过两个前缀和相减快速得到。例如texta [3, 1, 4, 1, 5, 9, 2, 6] 前缀和 s [0, 3, 4, 8, 9, 14, 23, 25, 31]如果要查询区间 [3,6][3,6] 的和即 a[3]a[4]a[5]a[6]415919a[3]a[4]a[5]a[6]415919可以直接计算 s[6]−s[2]23−419s[6]−s[2]23−419。这就是前缀和的基本思想用空间换时间把重复计算转化为一次预处理和若干次快速查询。2. 一维前缀和2.1 定义与递推公式设原数组为 a[1],a[2],…,a[n]a[1],a[2],…,a[n]定义前缀和数组 sss[i]∑j1ia[j]a[1]a[2]⋯a[i]s[i]j1∑ia[j]a[1]a[2]⋯a[i]特别地定义 s[0]0s[0]0表示空区间的前缀和。前缀和数组可以通过递推得到s[i]s[i−1]a[i]s[i]s[i−1]a[i]这个公式的含义是前 ii 个元素的和等于前 i−1i−1 个元素的和再加上第 ii 个元素。2.2 查询区间和对于任意区间 [l,r][l,r]其中 1≤l≤r≤n1≤l≤r≤n其元素和为∑jlra[j]s[r]−s[l−1]jl∑ra[j]s[r]−s[l−1]理解前 rr 个元素的和减去前 l−1l−1 个元素的和剩下的就是第 ll 到第 rr 个元素的和。由于 s[0]0s[0]0当 l1l1 时公式依然成立s[r]−s[0]s[r]s[r]−s[0]s[r]这就是为什么我们通常把前缀和数组下标从 1 开始并设置 s[0]0s[0]0这样可以避免对左端点为 1 的情况进行特判。2.3 代码实现cpp#include bits/stdc.h using namespace std; const int MAXN 1e5 5; int n, q; long long a[MAXN], s[MAXN]; void build_prefix_sum() { s[0] 0; for (int i 1; i n; i) { s[i] s[i - 1] a[i]; } } long long query_sum(int l, int r) { return s[r] - s[l - 1]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n q; for (int i 1; i n; i) { cin a[i]; } build_prefix_sum(); while (q--) { int l, r; cin l r; cout query_sum(l, r) \n; } return 0; }说明数组下标从 1 开始方便处理边界。使用long long防止累加和溢出。预处理一次 O(n)O(n)每次查询 O(1)O(1)。如果题目输入输出量大建议使用scanf/printf或关闭同步的cin/cout。2.4 下标从 0 开始的注意事项有些题目给出的数组下标习惯从 0 开始。此时可以将前缀和数组定义为 s[i1]s[i1] 表示前 i1i1 个元素的和即cpp// a[0..n-1] // s[i] 表示 a[0] ... a[i-1] vectorlong long s(n 1, 0); for (int i 0; i n; i) { s[i 1] s[i] a[i]; } // 查询 [l, r] 闭区间0-based long long sum s[r 1] - s[l];或者仍然定义前缀和数组与原数组等长但需要处理左端点为 0 的情况。推荐统一使用“长度加一”的前缀和数组下标从 1 开始。2.5 时间复杂度与数据范围预处理时间复杂度O(n)O(n)单次查询时间复杂度O(1)O(1)总时间复杂度O(nq)O(nq)空间复杂度O(n)O(n)数据范围注意点如果数组元素值较大累加和可能超过int的范围。例如 n105n105每个元素 105105总和可达 10101010需要使用long long。如果前缀和用于哈希表注意键的范围。3. 二维前缀和3.1 定义与递推公式二维前缀和用于处理矩阵中的子矩阵求和问题。设原矩阵为 a[i][j]a[i][j]其中 1≤i≤n1≤i≤n1≤j≤m1≤j≤m。定义二维前缀和 s[i][j]s[i][j] 表示以 (1,1)(1,1) 为左上角以 (i,j)(i,j) 为右下角的子矩阵中所有元素的和s[i][j]∑x1i∑y1ja[x][y]s[i][j]x1∑iy1∑ja[x][y]递推公式s[i][j]s[i−1][j]s[i][j−1]−s[i−1][j−1]a[i][j]s[i][j]s[i−1][j]s[i][j−1]−s[i−1][j−1]a[i][j]推导理解要计算 s[i][j]s[i][j]可以先加上上方矩形 s[i−1][j]s[i−1][j]即前 i−1i−1 行、前 jj 列的和再加上左方矩形 s[i][j−1]s[i][j−1]即前 ii 行、前 j−1j−1 列的和。但这样左上角的矩形 s[i−1][j−1]s[i−1][j−1] 被重复加了一次所以减去。最后加上当前元素 a[i][j]a[i][j]。3.2 查询子矩阵和如果要查询以 (x1,y1)(x1,y1) 为左上角、(x2,y2)(x2,y2) 为右下角的子矩阵和其中 1≤x1≤x2≤n1≤x1≤x2≤n1≤y1≤y2≤m1≤y1≤y2≤m公式为sums[x2][y2]−s[x1−1][y2]−s[x2][y1−1]s[x1−1][y1−1]sums[x2][y2]−s[x1−1][y2]−s[x2][y1−1]s[x1−1][y1−1]推导理解从整个大矩形 s[x2][y2]s[x2][y2] 中减去上方多余部分 s[x1−1][y2]s[x1−1][y2]第 11 行到第 x1−1x1−1 行第 11 列到第 y2y2 列再减去左方多余部分 s[x2][y1−1]s[x2][y1−1]第 11 行到第 x2x2 行第 11 列到第 y1−1y1−1 列。但左上角的小矩形 s[x1−1][y1−1]s[x1−1][y1−1] 被重复减了两次所以再加回来。3.3 代码实现cpp#include bits/stdc.h using namespace std; const int MAXN 1005; const int MAXM 1005; int n, m, q; long long a[MAXN][MAXM]; long long s[MAXN][MAXM]; void build_prefix_sum_2d() { for (int i 1; i n; i) { for (int j 1; j m; j) { s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] a[i][j]; } } } long long query_sum_2d(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]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m q; for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; } } build_prefix_sum_2d(); while (q--) { int x1, y1, x2, y2; cin x1 y1 x2 y2; cout query_sum_2d(x1, y1, x2, y2) \n; } return 0; }3.4 图形化理解与示例假设有一个 3×33×3 的矩阵texta: 1 2 3 4 5 6 7 8 9构建二维前缀和计算 s[1][1]s[1][1]texts[1][1] s[0][1] s[1][0] - s[0][0] a[1][1] 0 0 - 0 1 1计算 s[1][2]s[1][2]texts[1][2] s[0][2] s[1][1] - s[0][1] a[1][2] 0 1 - 0 2 3依次计算最终前缀和矩阵为texts: 1 3 6 5 12 21 12 27 45查询子矩阵 (2,2)(2,2) 到 (3,3)(3,3)textsum s[3][3] - s[1][3] - s[3][1] s[1][1] 45 - 6 - 12 1 28验证a[2][2]a[2][3]a[3][2]a[3][3]568928a[2][2]a[2][3]a[3][2]a[3][3]568928正确。二维前缀和的时间复杂度预处理 O(nm)O(nm)单次查询 O(1)O(1)总 O(nmq)O(nmq)。空间复杂度 O(nm)O(nm)。4. 前缀和与差分差分是前缀和的逆运算两者经常结合使用。前缀和解决“静态区间查询”差分解决“动态区间修改后一次查询”的问题。4.1 一维差分问题给定长度为 nn 的数组 aa初始全为 0 或给定值有 qq 次操作每次操作将区间 [l,r][l,r] 中每个元素加上 xx。最后输出修改后的数组。如果直接每次暴力修改时间复杂度 O(nq)O(nq)。使用差分可以做到 O(nq)O(nq)。差分数组定义设原数组为 aa定义差分数组 ddd[i]a[i]−a[i−1]d[i]a[i]−a[i−1]其中 a[0]0a[0]0。由差分数组可以通过前缀和还原原数组a[i]d[1]d[2]⋯d[i]a[i]d[1]d[2]⋯d[i]这正是前缀和的递推。区间修改操作要将区间 [l,r][l,r] 中所有元素加上 xx只需d[l]xd[l]xd[r1]−xd[r1]−x当对 dd 做前缀和时从 ll 开始每个位置会累加上 xx直到 r1r1 处减去 xx之后的位置不再受影响。代码cpp#include bits/stdc.h using namespace std; const int MAXN 1e5 5; int n, q; long long a[MAXN], d[MAXN]; int main() { cin n q; for (int i 1; i n; i) { cin a[i]; d[i] a[i] - a[i-1]; // 构建差分数组 } while (q--) { int l, r, x; cin l r x; d[l] x; if (r 1 n) d[r 1] - x; // 注意越界 } // 对差分数组求前缀和还原修改后的数组 for (int i 1; i n; i) { a[i] a[i-1] d[i]; cout a[i] ; } cout \n; return 0; }4.2 二维差分二维差分用于处理“对多个子矩阵进行加法操作最后输出整个矩阵”的问题。定义设原矩阵为 aa二维差分矩阵为 dd。它们满足a[i][j]∑x1i∑y1jd[x][y]a[i][j]x1∑iy1∑jd[x][y]即 aa 是 dd 的二维前缀和。构建方法若原矩阵 aa 已知可以通过以下方式构建 dd相当于对一个初始全 0 的矩阵对每个 1×11×1 的子矩阵加上 a[i][j]a[i][j]d[i][j]a[i][j]−a[i−1][j]−a[i][j−1]a[i−1][j−1]d[i][j]a[i][j]−a[i−1][j]−a[i][j−1]a[i−1][j−1]子矩阵修改操作要对以 (x1,y1)(x1,y1) 为左上角、(x2,y2)(x2,y2) 为右下角的子矩阵中每个元素加上 xx执行d[x1][y1]xd[x1][y1]xd[x21][y1]−xd[x21][y1]−xd[x1][y21]−xd[x1][y21]−xd[x21][y21]xd[x21][y21]x最后对 dd 做二维前缀和即可得到修改后的矩阵。代码框架cppint n, m, q; long long d[MAXN][MAXM]; void add(int x1, int y1, int x2, int y2, int x) { d[x1][y1] x; if (x2 1 n) d[x2 1][y1] - x; if (y2 1 m) d[x1][y2 1] - x; if (x2 1 n y2 1 m) d[x2 1][y2 1] x; } // 最后还原 for (int i 1; i n; i) { for (int j 1; j m; j) { d[i][j] d[i-1][j] d[i][j-1] - d[i-1][j-1]; // 此时 d[i][j] 就是修改后的 a[i][j] } }4.3 差分与前缀和的关系前缀和原数组 → 前缀和数组用于快速查询区间和。差分原数组 → 差分数组用于快速进行区间修改。两者互为逆运算差分数组的前缀和就是原数组前缀和数组的差分就是原数组。很多题目会结合两者先利用差分进行多次区间修改再利用前缀和还原或查询。5. 前缀和与子段和问题任意一个子段 [l,r][l,r] 的和都可以表示为两个前缀和的差∑ilra[i]s[r]−s[l−1]il∑ra[i]s[r]−s[l−1]这个性质非常强大许多子段和问题都可以转化为对前缀和数组的分析。5.1 子段和与两个前缀和的差对于固定的右端点 rr子段 [l,r][l,r] 的和只取决于左端点 llsums[r]−s[l−1]sums[r]−s[l−1]其中 l≤rl≤r所以 l−1l−1 的范围是 00 到 r−1r−1。因此如果我们想要最大/最小/满足某种条件的子段和可以枚举右端点 rr然后在 s[0..r−1]s[0..r−1] 中寻找合适的前缀和值。5.2 最大子段和问题给定一个长度为 nn 的整数数组可能包含负数求它的一个连续子段使得子段和最大。前缀和做法枚举右端点 rr子段和为 s[r]−s[l−1]s[r]−s[l−1]。要使其最大就需要在 l≤rl≤r 的前提下让 s[l−1]s[l−1] 尽可能小。因此可以维护一个变量min_pre表示已经遍历过的前缀和的最小值。对于每个 rr最大子段和候选为s[r]−min0≤krs[k]s[r]−0≤krmins[k]同时更新答案并更新min_pre。代码cpp#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorlong long a(n 1), s(n 1); for (int i 1; i n; i) { cin a[i]; s[i] s[i-1] a[i]; } long long min_pre 0; // s[0] 0 long long ans LLONG_MIN; for (int i 1; i n; i) { ans max(ans, s[i] - min_pre); min_pre min(min_pre, s[i]); } cout ans \n; return 0; }复杂度O(n)O(n)与经典的 Kadane 算法相同但这是从前缀和角度理解的。5.3 和为 K 的子数组问题给定一个整数数组可能有负数求连续子数组和为 kk 的个数。暴力做法是枚举所有子数组时间复杂度 O(n2)O(n2)。如果 nn 达到 105105会超时。前缀和 哈希表优化对于子数组 [l,r][l,r]和为 kk 等价于s[r]−s[l−1]ks[r]−s[l−1]k即s[l−1]s[r]−ks[l−1]s[r]−k我们可以从左到右遍历右端点 rr用一个哈希表统计已经出现过的前缀和值及其出现次数。对于当前右端点 rr我们需要知道有多少个左端点 l−1l−1 满足 s[l−1]s[r]−ks[l−1]s[r]−k也就是哈希表中键为 s[r]−ks[r]−k 的值。遍历前初始化哈希表cnt[0] 1因为空前缀和 s[0]0s[0]0 是一个合法的左端点。代码cpp#include bits/stdc.h using namespace std; int main() { int n, k; cin n k; vectorint a(n); for (int i 0; i n; i) cin a[i]; unordered_maplong long, int cnt; cnt[0] 1; // 空前缀 long long s 0; long long ans 0; for (int i 0; i n; i) { s a[i]; // 需要 s - k 出现了多少次 if (cnt.count(s - k)) { ans cnt[s - k]; } cnt[s]; } cout ans \n; return 0; }注意如果数组中元素可能很大前缀和用long long。unordered_map在极端情况下可能被卡到 O(n2)O(n2)若题目卡常可以使用map或手写哈希。该算法时间复杂度 O(n)O(n)空间复杂度 O(n)O(n)。5.4 和为 K 的倍数的子数组问题求连续子数组的和能被 kk 整除的个数。子数组和为 kk 的倍数即(s[r]−s[l−1])%k0(s[r]−s[l−1])%k0等价于s[r]%ks[l−1]%ks[r]%ks[l−1]%k因此只需要统计每个余数出现的前缀和个数。对于当前前缀和 s[i]s[i]它与之前所有同余的前缀和都能组成一个满足条件的子数组。注意负数取模在 C 中可能得到负余数可以统一转为非负((s%k)k)%k((s%k)k)%k代码cpp#include bits/stdc.h using namespace std; int main() { int n, k; cin n k; vectorint a(n); for (int i 0; i n; i) cin a[i]; vectorint cnt(k, 0); cnt[0] 1; long long s 0; long long ans 0; for (int i 0; i n; i) { s a[i]; int mod ((s % k) k) % k; ans cnt[mod]; cnt[mod]; } cout ans \n; return 0; }6. 前缀和的变体前缀和的思想不仅限于加法还可以推广到其他满足结合律且存在逆运算的操作。6.1 前缀异或和异或运算满足结合律和交换律且每个元素自己的逆元就是它本身因为 x⊕x0x⊕x0。定义前缀异或和x[i]a[1]⊕a[2]⊕⋯⊕a[i]x[i]a[1]⊕a[2]⊕⋯⊕a[i]递推x[i]x[i−1]⊕a[i]x[i]x[i−1]⊕a[i]区间 [l,r][l,r] 的异或和a[l]⊕a[l1]⊕⋯⊕a[r]x[r]⊕x[l−1]a[l]⊕a[l1]⊕⋯⊕a[r]x[r]⊕x[l−1]应用示例求有多少个子数组的异或和为 0。因为异或和为 0 等价于两个前缀异或和相等所以可以用哈希表统计相同前缀异或值出现的次数。cppunordered_mapint, int cnt; cnt[0] 1; int cur 0; long long ans 0; for (int i 0; i n; i) { cur ^ a[i]; ans cnt[cur]; cnt[cur]; }6.2 前缀乘积定义前缀乘积p[i]a[1]×a[2]×⋯×a[i]p[i]a[1]×a[2]×⋯×a[i]如果数组元素都不是 0并且我们在模一个质数的环境下可以使用乘法逆元来求区间乘积∏jlra[j]p[r]×inv(p[l−1])(modM)jl∏ra[j]p[r]×inv(p[l−1])(modM)但如果数组中有 0则不能直接使用逆元。此时需要特殊处理 0 的位置或者使用线段树等数据结构。6.3 前缀最大值/最小值定义前缀最大值preMax[i]max(preMax[i−1],a[i])preMax[i]max(preMax[i−1],a[i])前缀最小值类似。前缀最值可以快速查询“从头到某个位置的最大/最小值”但不能像前缀和那样通过差值来获得区间最值。区间最值通常使用 ST 表、线段树等。前缀最值在动态规划优化中很常见例如维护最小前缀和来求最大子段和。6.4 高维前缀和简介高维前缀和SOS DP子集动态规划是对多维数组进行前缀和常用于处理子集和问题。例如给定 2n2n 个值 f[mask]f[mask]求对于每个 maskmask其所有子集的 ff 值之和。具体做法是按每个二进制位进行 DPcppfor (int i 0; i n; i) { for (int mask 0; mask (1 n); mask) { if (mask (1 i)) { f[mask] f[mask ^ (1 i)]; } } }该算法时间复杂度 O(n⋅2n)O(n⋅2n)。虽然 CSP-J 较少涉及但在 CSP-S 中可能会遇到。7. 经典例题精讲7.1 一维前缀和模板题题目描述给定 nn 个数qq 次询问每次询问一个区间 [l,r][l,r] 的和。输入格式第一行两个整数 n,qn,q。第二行 nn 个整数。接下来 qq 行每行两个整数 l,rl,r。输出格式对于每次询问输出区间和。数据范围1≤n,q≤1051≤n,q≤105元素绝对值不超过 105105。分析直接使用一维前缀和模板即可。代码cpp#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin n q; vectorlong long s(n 1, 0); for (int i 1; i n; i) { int x; cin x; s[i] s[i-1] x; } while (q--) { int l, r; cin l r; cout s[r] - s[l-1] \n; } return 0; }7.2 二维前缀和模板题题目描述给定一个 n×mn×m 的矩阵qq 次询问每次询问一个子矩阵的和。输入格式第一行三个整数 n,m,qn,m,q。接下来 nn 行每行 mm 个整数。接下来 qq 行每行四个整数 x1,y1,x2,y2x1,y1,x2,y2。输出格式对于每次询问输出子矩阵和。分析使用二维前缀和模板。代码cpp#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin n m q; vectorvectorlong long s(n 1, vectorlong long(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { int x; cin x; s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] x; } } while (q--) { int x1, y1, x2, y2; cin x1 y1 x2 y2; long long ans s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1]; cout ans \n; } return 0; }7.3 最大加权矩形题目来源洛谷 P1719 最大加权矩形也可作为最大子段和的二维扩展题目描述给定一个 n×nn×n 的矩阵求一个子矩阵使得子矩阵内所有元素的和最大。数据范围1≤n≤1201≤n≤120矩阵元素可能为负数。分析如果直接枚举所有子矩阵子矩阵有 O(n4)O(n4) 个不可行。但可以枚举矩阵的上下边界将二维问题压缩成一维。具体做法枚举上边界top和下边界bottop≤bottop≤bot。将top到bot行之间的每一列的元素相加得到一个一维数组colSum[j]表示第j列在当前上下边界之间的元素和。对这个一维数组求最大子段和。所有上下边界组合的最大子段和的最大值即为答案。如果直接每次计算colSum需要 O(n)O(n)总复杂度 O(n3)O(n3)因为上下边界 O(n2)O(n2)每次求最大子段和 O(n)O(n)计算列和也需要 O(n)O(n) 但可以优化。当 n≤120n≤120 时O(n3)O(n3) 可行。优化计算列和可以用一维前缀和维护每列的前缀和这样对于固定的上下边界每列的区间和可以 O(1)O(1) 得到。代码cpp#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorvectorint a(n 1, vectorint(n 1)); vectorvectorlong long colPrefix(n 1, vectorlong long(n 1, 0)); for (int i 1; i n; i) { for (int j 1; j n; j) { cin a[i][j]; // 每列的前缀和方便快速求 [top,bot] 行第 j 列的和 colPrefix[i][j] colPrefix[i-1][j] a[i][j]; } } long long ans LLONG_MIN; for (int top 1; top n; top) { for (int bot top; bot n; bot) { // 压缩成一维数组 vectorlong long colSum(n 1, 0); for (int j 1; j n; j) { colSum[j] colPrefix[bot][j] - colPrefix[top-1][j]; } // 求一维最大子段和 long long cur 0; long long maxSum LLONG_MIN; for (int j 1; j n; j) { cur max(colSum[j], cur colSum[j]); maxSum max(maxSum, cur); } ans max(ans, maxSum); } } cout ans \n; return 0; }复杂度O(n3)O(n3)对于 n120n120 足够。7.4 领地选择题目来源洛谷 P2004 领地选择题目描述给定一个 n×mn×m 的矩阵要求选择一个 c×cc×c 的正方形区域使得区域内元素和最大。输出正方形左上角的坐标。分析枚举所有可能的正方形左上角 (i,j)(i,j)利用二维前缀和 O(1)O(1) 计算每个 c×cc×c 正方形的和取最大值。正方形右下角为 (ic−1,jc−1)(ic−1,jc−1)需要保证不越界。代码cpp#include bits/stdc.h using namespace std; int main() { int n, m, c; cin n m c; vectorvectorlong long s(n 1, vectorlong long(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { int x; cin x; s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] x; } } long long best LLONG_MIN; int ansX 1, ansY 1; for (int i 1; i c - 1 n; i) { for (int j 1; j c - 1 m; j) { int x2 i c - 1; int y2 j c - 1; long long sum s[x2][y2] - s[i-1][y2] - s[x2][j-1] s[i-1][j-1]; if (sum best) { best sum; ansX i; ansY j; } } } cout ansX ansY \n; return 0; }7.5 地毯题目来源洛谷 P3397 地毯题目描述在 n×nn×n 的矩阵上铺 mm 块地毯每块地毯覆盖一个子矩阵求最后每个位置被多少块地毯覆盖。数据范围n,m≤1000n,m≤1000。分析这是二维差分的经典应用。对每块地毯覆盖的子矩阵执行二维差分加法操作最后对差分矩阵做二维前缀和即可得到每个位置的覆盖数。代码cpp#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorint d(n 2, vectorint(n 2, 0)); for (int k 0; k m; k) { int x1, y1, x2, y2; cin x1 y1 x2 y2; d[x1][y1] 1; d[x2 1][y1] - 1; d[x1][y2 1] - 1; d[x2 1][y2 1] 1; } // 二维前缀和还原 for (int i 1; i n; i) { for (int j 1; j n; j) { d[i][j] d[i-1][j] d[i][j-1] - d[i-1][j-1]; cout d[i][j] ; } cout \n; } return 0; }7.6 光骓者的荣耀题目来源洛谷 P5638 光骓者的荣耀题目描述有一条长度为 nn 的路路上有 n−1n−1 个传送点第 ii 个传送点可以将人从 ii 传到 ikik。给定相邻站点之间的耗时求从 1 到 nn 的最短时间允许使用一次传送或者不使用。分析该题可以转化为求一段连续长度为 kk 的区间和的最大值然后用总路程减去这个最大值因为传送可以跳过这段路程。先计算出相邻站点之间的时间数组然后求前缀和枚举长度为 kk 的区间求其和的最大值。答案 总时间 - 最大区间和。代码cpp#include bits/stdc.h using namespace std; int main() { int n, k; cin n k; vectorlong long a(n); // a[1..n-1] 表示从 i 到 i1 的时间 vectorlong long s(n 1, 0); for (int i 1; i n - 1; i) { cin a[i]; s[i] s[i-1] a[i]; } long long total s[n-1]; long long maxSkip 0; for (int i 1; i k - 1 n - 1; i) { long long seg s[i k - 1] - s[i - 1]; maxSkip max(maxSkip, seg); } cout total - maxSkip \n; return 0; }7.7 和为 K 的子数组题目描述给定一个整数数组和一个整数 kk求该数组中和为 kk 的连续子数组的个数。分析已在 5.3 节详细讲解使用前缀和 哈希表。代码cpp#include bits/stdc.h using namespace std; int main() { int n, k; cin n k; vectorint a(n); for (int i 0; i n; i) cin a[i]; unordered_maplong long, int cnt; cnt[0] 1; long long s 0; long long ans 0; for (int i 0; i n; i) { s a[i]; if (cnt.count(s - k)) { ans cnt[s - k]; } cnt[s]; } cout ans \n; return 0; }7.8 异或和为 0 的子数组题目描述给定一个整数数组求异或和为 0 的连续子数组的个数。分析一个子数组的异或和为 0 等价于其左右两端的前缀异或和相等。因此统计相同前缀异或值的出现次数。代码cpp#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; unordered_mapint, int cnt; cnt[0] 1; int cur 0; long long ans 0; for (int i 0; i n; i) { cur ^ a[i]; ans cnt[cur]; cnt[cur]; } cout ans \n; return 0; }8. 易错点与代码技巧下标从 1 开始使用前缀和时推荐将数组下标从 1 开始并设置 s[0]0s[0]0。这样可以避免左端点为 1 时的特判代码更简洁。数据类型前缀和累加后可能超过int范围务必使用long long。尤其是二维前缀和元素数量可能达到 106106累加和很容易超过 231−1231−1。二维前缀和边界查询子矩阵时公式中的 x1−1x1−1、y1−1y1−1 可能为 0这是合法的因为 s[0][j]0s[0][j]0、s[i][0]0s[i][0]0。但必须确保前缀和数组的第 0 行和第 0 列初始化为 0。差分数组越界一维差分中d[r1]d[r1] 可能越界需要判断 r1≤nr1≤n。二维差分中需要判断 x21≤nx21≤n 和 y21≤my21≤m。哈希表性能C 的unordered_map在最坏情况下可能被构造的数据卡成 O(n)O(n) 单次操作导致整体 O(n2)O(n2)。如果题目对性能要求高可以使用map稳定 O(logn)O(logn)或手写哈希表。负数取模在求“和为 K 的倍数”时C 中负数取模可能得到负数需要转换为非负余数((s % k) k) % k。输入输出优化当 n,qn,q 达到 106106 级别时使用ios::sync_with_stdio(false); cin.tie(nullptr);或直接使用scanf/printf避免 I/O 成为瓶颈。前缀和的逆运算前缀和和差分是互逆的。如果题目中既有区间修改又有区间查询单纯的前缀和无法胜任需要树状数组或线段树。注意区分题目是静态查询还是动态修改。子段和问题任意子段和都可以表示为两个前缀和之差因此很多子段和问题可以转化为在前缀和数组中寻找满足某种关系的两个位置常常结合哈希表、双指针、二分等技巧。空间优化对于一维前缀和有时可以直接在原数组上累加节省空间。但要注意保留原数组以备后续使用。9. 总结前缀和是一种非常基础但极其重要的预处理技巧它将“区间查询”从 O(n)O(n) 降到 O(1)O(1)在静态数组场景下具有巨大优势。本讲义重点内容回顾一维前缀和s[i]s[i−1]a[i]s[i]s[i−1]a[i]查询 [l,r][l,r] 为 s[r]−s[l−1]s[r]−s[l−1]。二维前缀和递推公式 s[i][j]s[i−1][j]s[i][j−1]−s[i−1][j−1]a[i][j]s[i][j]s[i−1][j]s[i][j−1]−s[i−1][j−1]a[i][j]查询子矩阵和公式类似。差分前缀和的逆运算用于快速进行区间修改。子段和问题利用 s[r]−s[l−1]s[r]−s[l−1]结合最小前缀、哈希表等方法解决最大子段和、和为 K 的子数组等问题。变体前缀异或和、前缀乘积、前缀最值等。前缀和不仅在基础题中直接出现还常常作为复杂算法的预处理步骤。例如在动态规划中前缀和可以用于快速计算状态转移中的区间和在二维问题中二维前缀和可以快速判断子矩阵是否满足条件在字符串问题中前缀和可以用于快速计算区间内字符出现的次数等。掌握前缀和并能灵活运用其变形和组合是 CSP-J/S 复赛中拿到基础分的关键。10. 练习题推荐以下题目适合练习前缀和与差分难度逐渐递增洛谷 P8218 【深进1.例1】求区间和一维前缀和模板。洛谷 P1115 最大子段和前缀和 最小前缀。洛谷 P2004 领地选择二维前缀和枚举正方形。洛谷 P1719 最大加权矩形二维前缀和 压缩成一维最大子段和。洛谷 P3397 地毯二维差分模板。洛谷 P5638 光骓者的荣耀一维前缀和求最大区间和。洛谷 P3131 [USACO16JAN] Subsequences Summing to Sevens S前缀和 余数统计。洛谷 P2697 宝石串前缀和差值统计。洛谷 P1387 最大正方形二维前缀和 二分或枚举边长。洛谷 P2280 [HNOI2003] 激光炸弹二维前缀和注意坐标范围。LeetCode 560 和为 K 的子数组前缀和 哈希表。LeetCode 974 和可被 K 整除的子数组前缀和 余数统计。AcWing 795 前缀和一维模板。AcWing 796 子矩阵的和二维模板。AcWing 797 差分一维差分模板。AcWing 798 差分矩阵二维差分模板。通过大量练习可以熟练掌握前缀和的构建、查询以及与其他算法结合使用的技巧为 CSP-J/S 的复赛打下坚实基础。