前缀和 (Prefix Sum) 完全指南：一维 / 二维 / 差分 / 哈希延伸

处理“区间求和 / 区间统计”类问题时最基础也最实用的一把瑞士军刀就是前缀和 (Prefix Sum)。一次O(n)预处理换来O(1)区间查询在二维上是O(nm)换O(1)。本文从一维讲到二维再到差分、前缀和 哈希表子数组和等于k、前缀异或每节给出可直接套用的 C 模板和典型 LeetCode 题目。1. 什么时候想到前缀和看到下面几种关键词基本都可以往前缀和上靠区间和 / 区间平均 / 区间计数多次查询连续子数组和等于 / 大于 / 可被某数整除二维矩形区域和某类事件的累计计数比如“到下标i为止出现了多少个偶数”和差分配合区间修改、单点查询如果一个量f(i)可以写成f(i) f(i-1) a[i]这种线性累加形式它就是前缀和的候选。2. 一维前缀和模板定义prefix[i]为数组a[0..i-1]的累加和长度n1prefix[0] 0prefix[i] a[0] a[1] ... a[i-1]于是任意闭区间[l, r]0 ≤ l ≤ r ≤ n-1的和a[l] a[l1] ... a[r] prefix[r1] - prefix[l]习惯用“长度 n1、下标从 1 开始”的前缀和数组可以把[l, r]的和统一写成prefix[r1] - prefix[l]不用再特判l 0。C 模板#includevectorstructPrefixSum1D{std::vectorlonglongprefix;explicitPrefixSum1D(conststd::vectorinta):prefix(a.size()1,0){for(std::size_t i0;ia.size();i){prefix[i1]prefix[i]a[i];}}longlongrangeSum(intl,intr)const{returnprefix[r1]-prefix[l];}};注意用long long防止累加溢出[l, r]这里是闭区间如果题目给的是半开区间[l, r)就改成prefix[r] - prefix[l]预处理是O(n)每次查询是O(1)非常适合多次查询的场景。典型题LeetCode 303 / 304区间和查询 I / IILeetCode 724寻找数组的中心下标LeetCode 1991找到数组的中间位置3. 二维前缀和矩形区域和定义S[i][j]为矩阵左上角到(i-1, j-1)的子矩阵和同样留出第 0 行/列S[i][j] sum of a[r][c] (0 r i, 0 c j)递推两加一减S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] a[i-1][j-1]查询子矩阵(r1, c1)到(r2, c2)闭区间的和两减一加一减对称地sum(r1, c1, r2, c2) S[r21][c21] - S[r1][c21] - S[r21][c1] S[r1][c1]C 模板#includevectorstructPrefixSum2D{intn0,m0;std::vectorstd::vectorlonglongS;explicitPrefixSum2D(conststd::vectorstd::vectorinta){nstatic_castint(a.size());mn?static_castint(a[0].size()):0;S.assign(n1,std::vectorlonglong(m1,0));for(inti1;in;i){for(intj1;jm;j){S[i][j]S[i-1][j]S[i][j-1]-S[i-1][j-1]a[i-1][j-1];}}}longlongrangeSum(intr1,intc1,intr2,intc2)const{returnS[r21][c21]-S[r1][c21]-S[r21][c1]S[r1][c1];}};口诀“前缀是两加一减查询是两减一加”中心思想都是容斥。典型题LeetCode 304二维区域和检索 - 矩阵不可变LeetCode 1314矩阵区域和LeetCode 1074元素和为目标值的子矩阵数二维 哈希前缀和见第 5 节4. 差分数组区间修改 单点查询差分是前缀和的“逆运算”。设diff[i] a[i] - a[i-1]则a[i] diff[0] diff[1] ... diff[i]即a是diff的前缀和。这带来一个好处对原数组区间[l, r]都加上x等价于diff[l] x; diff[r1] - x;只改两个点。当你需要执行多次区间加最后再整体查询所有位置的值差分 一次前缀和就能O(n q)完成比每次遍历O(nq)高效得多。C 模板#includevectorstructDifference1D{std::vectorlonglongdiff;explicitDifference1D(intn):diff(n1,0){}explicitDifference1D(conststd::vectorinta):diff(a.size()1,0){for(std::size_t i0;ia.size();i){diff[i]a[i];diff[i1]-a[i];}}voidrangeAdd(intl,intr,longlongx){diff[l]x;diff[r1]-x;}std::vectorlonglongresult()const{std::vectorlonglonga(diff.size()-1);longlongcur0;for(std::size_t i0;ia.size();i){curdiff[i];a[i]cur;}returna;}};典型题LeetCode 1109航班预订统计LeetCode 1893检查是否区域内所有整数都被覆盖LeetCode 1094拼车二维差分思路完全类似把“两加一减”的递推搬到差分矩阵上就能做二维区间加 最后一次前缀和。5. 前缀和 哈希表子数组和等于k如果问的不是“区间和”而是“有多少个连续子数组它们的和等于k”就要把前缀和和哈希表结合起来sum(l, r) prefix[r1] - prefix[l] k prefix[l] prefix[r1] - k于是每扫到一个前缀和pre问题就变成之前出现过多少次pre - k用一个unordered_maplong long, int记录前缀和出现次数即可#includeunordered_map#includevectorintsubarraySum(conststd::vectorintnums,intk){std::unordered_maplonglong,intcnt;cnt[0]1;// 空前缀longlongpre0;intanswer0;for(intx:nums){prex;autoitcnt.find(pre-k);if(it!cnt.end())answerit-second;cnt[pre];}returnanswer;}这招的通用模式是“目标条件可以写成prefix[r] - prefix[l]的形式”→ 用哈希表记录“以前见过哪些prefix/ 它们的某种特征”。常见变体和为k的倍数对pre取模k哈希键用pre % k注意负数取模要归一化。奇偶次数 / 出现次数把前缀状态压成bitmask再用哈希表LeetCode 1371 每个元音包含偶数次的最长子字符串。“连续且和为 0 的子数组”等价于prefix[l] prefix[r]直接哈希表找相同前缀和。典型题LeetCode 560和为k的子数组LeetCode 974和可被k整除的子数组LeetCode 523连续子数组和判断是否存在LeetCode 1074元素和为目标值的子矩阵数先固定行再对列向压成一维前缀和 哈希6. 前缀异或异或区间与“相等前缀”异或有一个与加法完全对偶的好性质a XOR a 0所以子数组异或也可以用前缀异或pre表示a[l] ^ a[l1] ^ ... ^ a[r] pre[r1] ^ pre[l]要求区间异或 某个值k→pre[l] pre[r1] XOR k依然是“哈希表找前缀”问题。要求区间异或为 0→pre[l] pre[r1]找重复前缀。模板和 “前缀和 哈希” 几乎一样只是把换成^#includeunordered_map#includevectorlonglongcountSubarrayXorEqualsK(conststd::vectorintnums,intk){std::unordered_mapint,longlongcnt;cnt[0]1;intpre0;longlonganswer0;for(intx:nums){pre^x;autoitcnt.find(pre^k);if(it!cnt.end())answerit-second;cnt[pre];}returnanswer;}典型题LeetCode 1310子数组异或查询纯前缀异或LeetCode 1442形成两个异或相等数组的三元组数目LeetCode 1915最美子字符串的数目前缀 bitmask 哈希7. 常见坑与实现建议下标一致性推荐统一采用prefix[0] 0、长度n1的写法区间[l, r]→prefix[r1] - prefix[l]否则一不小心就越界 / 少算一位。溢出prefix用long long二维尤其容易在n, m和a[i][j]都较大时爆int。负数取模和可被k整除类题目pre % k可能是负数要统一成((pre % k) k) % k再做哈希键。多组查询 vs 单次查询如果只查一次朴素O(n)就够了前缀和/差分的价值体现在大量查询或区间修改。与滑动窗口区分滑动窗口要求单调性扩右必然让某量单调变化前缀和 哈希表不依赖单调性能处理含负数的子数组和问题。二维进一步优化二维区间和的升级题1074、363核心套路是“枚举上下边界把列向压成一维再前缀和 / 哈希”。8. 一句话总结一维、二维区间查询→前缀和 容斥。区间修改、单点/整体查询→差分本质上仍是前缀和。统计满足某条件的子数组个数→前缀和 哈希表。异或类题目 →前缀异或 哈希表和“ 换 ^”的套路同构。记住“只要一个量满足f(l..r) g(r) - g(l)或g(r) XOR g(l)就可以把它前缀化。”9. 推荐刷题顺序303 / 304一维 / 二维区间和 —— 入门模板题。1109 / 1094差分 —— 区间加的“必套路”。560 / 974 / 523前缀和 哈希 —— 关键思维训练。1310 / 1442 / 1915前缀异或 哈希 —— 熟悉异或版模板。1074 / 363二维 哈希 / 最大子矩阵和 —— 把一维套路升到二维。