刷LeetCode刷到一定量之后你会发现前缀和就像一把“万能钥匙”它能把区间求和从O(n)压到O(1)也能配合哈希表把子数组统计问题从O(n²)压到O(n)。在上一个专题里我详细讲过最基础的一维前缀和构造、区域和检索、中心下标这类直接套模板的题。但只掌握基础版远远不够——面试里真正拉开差距的是前缀和与哈希表、二维矩阵前缀和、动态前缀和树状数组组合出的进阶玩法。这篇“前缀和专题二”我定位成“从静态到动态、从一维到二维、从暴力到哈希”的进阶篇重点解决三个痛点第一当题目要求统计“和为K的子数组个数”时为什么暴力枚举一定会超时哈希表如何一步到位第二二维矩阵里的区域求和怎么用容斥原理做O(1)查询第三如果数组会被多次修改静态前缀和失效后树状数组如何继续扛大梁。本文所有题目都来自LeetCode高频题适合已经刷完专题一、正准备冲击中等难度算法的读者。1. 从一维到二维前缀和进阶的两个方向1.1 哈希表优化的核心推导把枚举变成查表我们先回到一维场景。假设数组A定义前缀和数组pref[i]表示从A[0]加到A[i]的总和。那么任意子数组A[i..j]的和可以写成sum(i..j) pref[j] - pref[i-1]约定 pref[-1] 0这个公式是专题一的老朋友。问题在于当题目变成“统计有多少个子数组的和恰好等于 K”时很多人第一反应是枚举左右端点i和j对每一对计算pref[j] - pref[i-1] K是否成立。这个做法的时间复杂度是O(n²)在LeetCode上遇到n 10^5这种数据规模时直接TLE没商量。真正的突破口在公式变形pref[j] - pref[i-1] K pref[i-1] pref[j] - K注意这个变形的含义当我们遍历到位置j时不需要回头枚举i只需要回答一个问题——“在j之前有多少个前缀和的值等于pref[j] - K”。这正好是哈希表的看家本领把“找有没有某个历史前缀和”变成“统计历史前缀和的出现次数”。用一个字典记录每个前缀和值出现的次数遍历一遍数组边累加边查表时间复杂度直接降到O(n)。这里有一个新手常常想不通的点为什么遍历到j时要先查表再更新当前前缀和因为我们要找的是“在j之前的子数组”如果先把当前的前缀和加入字典就可能出现i j的退化情况空子数组导致计数错误。更严谨地说当前这一轮查询只能使用“历史”数据不能在更新之前就把pref[j]算进答案里。这个顺序问题我在第4节还会专门展开。1.2 二维前缀和的容斥原理一个公式吃遍矩阵一维前缀和解决的是数组上的区间问题二维前缀和解决的是矩阵上的区域问题。LeetCode 304二维区域和检索就是最典型的考查点核心思路和“看整张地图的累计面积”完全一样。定义一个二维前缀和矩阵pref[i][j]表示“从左上角(0,0)到(i,j)这个矩形区域内所有元素的和”。它的递推公式是pref[i][j] pref[i-1][j] pref[i][j-1] - pref[i-1][j-1] matrix[i][j]很多初学者会在这个公式上卡住尤其是那个“减一次pref[i-1][j-1]”的操作。我习惯这样理解pref[i-1][j]覆盖了上方区域pref[i][j-1]覆盖了左侧区域两者相加会把左上角的矩形重复计算一次所以必须减去pref[i-1][j-1]来抵消最后再加上当前位置的元素matrix[i][j]。这就像计算两个有重叠区域的集合的并集大小重叠部分必须扣掉一次——集合论里的容斥原理在矩阵里原样复刻。有了二维前缀和矩阵之后任意子矩阵(r1,c1)到(r2,c2)的区域和只需要O(1)时间sum(r1,c1,r2,c2) pref[r2][c2] - pref[r1-1][c2] - pref[r2][c1-1] pref[r1-1][c1-1]同样的容斥逻辑从大矩形里减去上方和左侧的区域再把左上角被多减的部分加回来。这里的关键是坐标边界的处理——r1-1、c1-1可能等于 -1所以建议把二维前缀和矩阵多开一行一列用“下标从1开始”的方式避开负数索引。这种做法我们写代码时会看到。1.3 动态前缀和的引入静态数组的困境一维、二维前缀和都有一个共同前提数组是静态的构建完成后不修改。但真实场景里经常出现“先求和、再改某个元素、再求和”的需求。如果每次修改后都重建前缀和数组单次重建O(n)、连续m次操作就是O(m·n)数据一上规模就扛不住。树状数组Fenwick Tree / Binary Indexed Tree就是为这个场景设计的它支持两个操作单点修改add(i, x)时间O(log n)前缀和查询sum(k)时间O(log n)。虽然单次查询比静态前缀和的O(1)慢但修改成本从O(n)降到了O(log n)在“修改与查询交替出现”的动态场景里是性价比极高的方案。热搜词里有一个很典型的例子对长度为16的序列查询前缀和sum(11)与单点修改add(3, x)。这个问题我放在第3节专门拆解因为它是理解树状数组背后二进制规律的最佳入口。2. 三连题拆解哈希表优化前缀和的三种经典模型2.1 LeetCode 560和为K的子数组题目要求统计数组中等和等于K的连续子数组的个数。这道题是前缀和哈希表的“祖师范例题”学会了它后面一大串变题都能秒解。先给出C实现class Solution { public: int subarraySum(vectorint nums, int k) { unordered_maplong long, int cnt; cnt[0] 1; // 前缀和为0的初始计数 long long sum 0; int ans 0; for (int x : nums) { sum x; // 查历史有多少个前缀和 sum - k auto it cnt.find(sum - k); if (it ! cnt.end()) ans it-second; // 更新当前前缀和的计数 cnt[sum]; } return ans; } };这段代码里有三个容易出问题的细节。第一个是cnt[0] 1的初始化。它代表的含义是在数组开始之前前缀和为0的情况已经出现过1次。为什么有这个必要考虑nums[0..j]这一整段元素的和恰好等于K的情况按公式推导需要找到一个i使得pref[i-1] pref[j] - K 0也就是存在“空前缀”作为起点。如果不提前把0放进哈希表这种“从头开始的子数组”就会被漏掉。我第一次写这道题时就是在这里栽的跟头漏掉了cnt[0]导致答案少了。第二个是查询与更新之间的顺序。必须先find(sum - k)再cnt[sum]这个顺序我在1.1节强调过。如果写反了先更新再查询会把“以当前元素结尾且长度恰好为整个前缀”的空子数组也算进去同时多算当前这一个前缀本身出现各种错误。LeetCode的测试用例设计得比较严格写反了在个别例子上可能碰巧通过但一旦出现多个连续元素和为K的情况就会暴露。第三个是数据类型问题。题目数据范围里nums是整数数组但前缀和在累加过程中可能超出int范围。C里我用long long来装sum和哈希表的键这是我在专题一就提到的习惯——前缀和相关的变量能开长整型就开长整型别留着 int 在临界边缘试探。Python不需要考虑溢出问题但逻辑完全一样。用Python复现一份class Solution: def subarraySum(self, nums: List[int], k: int) - int: cnt defaultdict(int) cnt[0] 1 ans 0 s 0 for x in nums: s x ans cnt[s - k] cnt[s] 1 return ans2.2 LeetCode 974和可被K整除的子数组这道题是560的变体但多了一个“整除”的约束导致处理方式完全不同。题目要求统计所有和能被K整除的连续子数组的个数。核心推导也不难子数组(i..j)的和能被K整除等价于pref[j] - pref[i-1]能被K整除等价于pref[j] % K pref[i-1] % K。所以问题变成了“统计前缀和模K相同的位置对”。这思路和560的“值相等”本质一样都是查表但这里查的是“模数相等”的计数。负数取模是这道题最大的坑。C和Java里负数的%运算结果是负数比如-7 % 3 -1但数学上我们希望余数的范围在[0, K-1]之间。如果不处理负数两个本应模数相同的前缀和会因为这个符号问题被错误地拆开。处理手法是统一转正模mod (sum % K K) % Ksum % K K先把负数补成(负数K)的正值再对K取一次模这样无论sum是正还是负都能得到[0, K-1]范围内的结果。这是这类整除题目通用的写法建议直接当成肌肉记忆。满分的实现class Solution { public: int subarraysDivByK(vectorint nums, int k) { unordered_mapint, int cnt; cnt[0] 1; int sum 0; int ans 0; for (int x : nums) { sum x; int mod (sum % k k) % k; ans cnt[mod]; cnt[mod]; } return ans; } };注意这里sum用int就行因为我们对它取模了sum本身不会无限增长——当然保险起见用long long也没问题。cnt[0] 1同样不能省它对应的是“从开头到当前位置的整段和能被K整除”的情况。补充一个优化点因为只需要记录模K的计数而K的取值范围可能很大最多3万用unordered_map完全没问题如果你确定K较小也可以直接用长度为K的vector数组来当计数器这样连哈希表的开销都省了。两种写法的正确性一致区别只在常数性能。2.3 LeetCode 525连续数组这道题换了个马甲给定一个只包含0和1的数组找最长连续子数组使得子数组中0和1的数量相等。如果直接想“0和1数量相等”可能会往滑动窗口方向想但0和1没有单调性滑动窗口不成立。正确的做法是把0映射成-1。这样一来“0和1数量相等”就等价于“把-1和1相加总和为0”。于是题目变成找最长的一段连续子数组其前缀和之差为0也就是两个位置的前缀和相等。用一个哈希表记录“某个前缀和第一次出现的下标”遍历时如果发现当前前缀和已经出现过说明从上次出现位置到当前位置之间总和为0就用当前位置与第一次出现位置的间隔更新答案。注意这里只需要记录第一次出现的位置因为我们要找最长的距离越早出现间隔越大。Python实现class Solution: def findMaxLength(self, nums: List[int]) - int: first {0: -1} # 前缀和为0首次出现在下标-1虚拟位置 s 0 ans 0 for i, x in enumerate(nums): s 1 if x 1 else -1 if s in first: ans max(ans, i - first[s]) else: first[s] i return ans这里first[0] -1非常重要。想象整个数组[0, 1]映射后是[-1, 1]前缀和分别是 -1 和 0。当遍历到第二个元素时前缀和变成0首次出现的位置是 -1因此长度是1 - (-1) 2正好是正确答案。如果不初始化0: -1这个全数组最优答案就会被漏掉。560题里的cnt[0] 1和这里的first[0] -1本质上都是“虚拟前缀”的初始化是哈希表方案的灵魂。2.4 三题对比什么时候查次数什么时候查下标如果你仔细看这三道题会发现它们共用同一个骨架但细节差异决定了“存什么、怎么查”题目哈希表记录的内容对应关系目标560 和为K的子数组前缀和的出现次数pref[j] - K出现的次数求子数组个数974 和可被K整除的子数组前缀和模K的出现次数模数相同的位置对求子数组个数525 连续数组前缀和第一次出现的下标前缀和相同的位置距离求最长子数组长度区别清晰了题目问“有几个”哈希表存次数题目问“最长”哈希表存首次下标。存次数的题里当前遍历到的位置可以重复与多个历史位置配对所以每个前缀和出现次数都要累加存下标的题里取最远的历史位置就够了所以只存首次出现。这个判断在面试时能帮你快速定位解法方向。3. 二维前缀和实战与树状数组扩展3.1 LeetCode 304二维区域和检索题目要求设计一个类初始化时传入矩阵之后反复调用sumRegion(r1, c1, r2, c2)查询子矩阵和。如果每次都暴力累加一次查询O(n²)多个查询一起到来时性能很差。二维前缀和把每次查询压到O(1)。我的实现习惯是让前缀和矩阵pref比原矩阵大一圈即pref.size() n1pref[0].size() m1所有下标从1开始。这样做的好处是不用单独判断r1-1或c1-1是否为负数——它们天然对应0行/0列值本来就是0。class NumMatrix { private: vectorvectorint pref; public: NumMatrix(vectorvectorint matrix) { int n matrix.size(), m matrix[0].size(); pref.assign(n 1, vectorint(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { pref[i][j] pref[i-1][j] pref[i][j-1] - pref[i-1][j-1] matrix[i-1][j-1]; } } } int sumRegion(int r1, int c1, int r2, int c2) { // 把题目给的0-based坐标转成1-based坐标 r1, c1, r2, c2; return pref[r2][c2] - pref[r1-1][c2] - pref[r2][c1-1] pref[r1-1][c1-1]; } };这段代码里的下标转换非常容易写错。构造pref时原矩阵matrix使用的是0-based下标而pref使用的是1-based下标所以填入值时是matrix[i-1][j-1]。查询时先把传入的r1, c1, r2, c2全部加1变成1-based坐标再套容斥公式。我见过很多初学者在这两个环节漏了-1或1结果区域偏移一个单位整题白写。3.2 树状数组动态前缀和的核心原理现在回到开头提到的那个具体问题维护长度n 16的序列查询前缀和sum(11)与单点修改add(3, x)。如果说静态前缀和是“一次建表永久查询”树状数组就是“修改和查询交替进行”的利器。它的底层依赖一个很聪明的二进制规律。树状数组内部维护一个数组tree[]下标从1开始。tree[i]管理的不只是A[i]一个元素而是一段连续区间区间长度等于lowbit(i)区间终点是i。这里的lowbit(i)定义是i (-i)即i的二进制表示中最低位的1所对应的数值。比如lowbit(3) 10011与1101按位与得0001值1lowbit(4) 40100与1100按位与得0100值4lowbit(6) 20110与1010按位与得0010值2lowbit(8) 81000与1000按位与得1000值8tree[i]负责的范围是[i - lowbit(i) 1, i]。所以tree[3]管理[3, 3]只有A[3]自己tree[4]管理[1, 4]这是前4个元素的和tree[6]管理[5, 6]这是第5到第6个元素的和tree[8]管理[1, 8]前8个元素的和tree[16]管理[1, 16]整个序列的和理解区间归属之后两个操作就一目了然了。查询前缀和sum(11)11的二进制是1011。先取tree[11]管理[11,11]然后去掉最低位的111 - lowbit(11) 11 - 1 10再取tree[10]管理[9,10]再去掉最低位的110 - lowbit(10) 10 - 2 8再取tree[8]管理[1,8]下一步8 - lowbit(8) 0结束。所以sum(11) tree[11] tree[10] tree[8]观察这三个下标111011、101010、81000每一步都在把最低位的1抹掉。这个过程正好把[1,11]拆成了三个不重叠的区间[11,11] [9,10] [1,8]。二进制下的“逐步消去最低位1”就是查询路径。单点修改add(3, x)给A[3]加上x那么所有管理到下标3的tree[i]都要同步更新。路径是从i 3开始每次给i加上lowbit(i)3 的二进制是0011lowbit 1更新tree[3]下一步3 1 44 的二进制是0100lowbit 4更新tree[4]下一步4 4 88 的二进制是1000lowbit 8更新tree[8]下一步8 8 1616 的二进制是10000lowbit 16更新tree[16]下一步32超出范围结束所以add(3, x)的更新路径是tree[3] - tree[4] - tree[8] - tree[16]为什么更新要沿着“加lowbit”走因为管理下标3的区间只可能是那些i - lowbit(i) 1 3 i的tree[i]。从3出发不断加上lowbit恰好能命中所有包含3的区间终点一个不多一个不少。这是二叉树藏在二进制里的“隐式结构”正因如此树状数组的查询和修改都能做到O(log n)。树状数组代码很短核心操作可以封装成两个函数class Fenwick { vectorint tree; int n; public: Fenwick(int n) : n(n), tree(n 1, 0) {} void add(int idx, int delta) { for (; idx n; idx idx -idx) { tree[idx] delta; } } int sum(int idx) { int res 0; for (; idx 0; idx - idx -idx) { res tree[idx]; } return res; } };在LeetCode里树状数组最常见的应用场景是“逆序对”“第K大”“区间和的动态维护”这类题目。你会看到它们的共同特征数组是可变的查询要求实时。静态前缀和解决不了这种问题线段树能解决但代码略重树状数组正好是性价比最高的折中方案。4. 常见问题与排查技巧实录4.1 哈希表初始化该写多少这是我们专题里命中率最高的Bug。560题和974题需要cnt[0] 1因为目标是统计子数组个数空前缀也是一种合法的“出现次数”。525题需要first[0] -1因为目标是求最长距离虚拟位置放在-1才让间隔计算正确。但并不是所有“前缀和哈希”题都需要这个初始化。比如统计“和为目标值的正数子数组个数且所有元素都为正数”时即使不初始化也能跑对因为不存在负数前缀和回落到0的情况。我的建议是不要盲目背初始化而是想清楚“前缀和为0的状态是否在数组开始之前就存在”。前文提到的三种模型中答案都是“存在”所以初始化必不可少。4.2 负数取模的隐蔽错误974题的负数取模问题我已经反复强调这里再补充一个排查技巧如果代码在C提交时偶发错误、但不使用负数测试用例时又全部通过大概率是取模符号问题。验证方法很简单打印所有前缀和取模后的结果看是否有负数出现。一旦出现负数立即套上(sum % k k) % k统一转正。这条经验也适用于其他带取模的算法题不只是前缀和。4.3 前缀和溢出的连锁反应前缀和累加过程中值可能远超单个元素的范围。比如数组元素最大10^9、长度10^5前缀和最大能达到10^14明显溢出32位int。溢出后的结果是未定义行为在C里可能表现为哈希表键变成负数或截断值导致所有计数全部错乱。排查时先在累加语句sum x处打个断点看sum是否异常再决定是改成long long还是用Python。LeetCode的C题解里几乎所有前缀和题都用long long存sum这不是小题大做而是经验之谈。注意long long的极限大约是9×10^18如果题目数据更大极少见还需要考虑__int128或取模压缩。4.4 二维前缀和的坐标偏移二维前缀和的三段式代码里坐标偏移是最容易错的地方。我的经验是构造前缀和矩阵时统一用1-based坐标查询时传入的0-based坐标先整体1再套公式。同时利用“多开一行一列”的技巧让边界的0值自然存在避免写一堆if判断。如果你在提交304时频繁越界优先检查三处构造pref时是否有matrix[i-1][j-1]的偏移查询时r1,c1是否做了1容斥公式中四个项的符号是否写对。把这三处当成一个固定的“三步走”检查清单基本能消灭这类错误。4.5 树状数组下标越界的边界处理树状数组的下标从1开始这是最容易出问题的地方。如果原数组长度是n初始化Fenwick(n)时分配n1个元素tree[0]不用。查询时如果传入下标0函数应该直接返回0修改时如果idx 0idx -idx也是0会导致死循环。所以在封装函数里对idx 0的情况做保护或者调用方保证下标至少从1开始。我在处理LeetCode题目时习惯把0-based下标统一1后再传给树状数组这样所有边界逻辑都归于“1..n”的标准区间。4.6 总结一份自查表常见问题典型表现解决方案哈希表未初始化边界状态答案比预期少尤其漏掉整段前缀初始化cnt[0]1或first[0]-1查询和更新顺序颠倒答案多出空子数组先查后更新负数取模整除相关题目偶发错误使用(x % k k) % k前缀和溢出哈希键异常、结果错乱累加变量用long long二维坐标偏移查询结果差一个单位或越界前缀和矩阵多开一圈、坐标1再套公式树状数组下标为0死循环或错误结果下标整体1封装时保护idx05. 专题二的核心套路复盘先判断题目类型写到这里我想把这些零散的知识点重新串联一下。前缀和进阶题其实就三种模型面试时拿到题可以先对号入座。第一种是连续子数组的“个数”问题典型特征是问“有多少个子数组满足某个条件”。解题框架是前缀和 哈希计数核心是把条件pref[j] - pref[i] target改写成pref[i] pref[j] - target用哈希表查历史次数。560、974都属于这一类区别只是等式右边换成了取模后的值。第二种是连续子数组的“最长长度”问题典型特征是问“最长的满足条件的连续子数组有多长”。解题框架是前缀和 哈希记录首次下标因为最长一定对应最早出现的位置。525和“和为零的最长子数组”都是这个套路。第三种是矩阵区域查询问题典型特征是在二维矩阵中多次查询任意矩形区域的和。解题框架是二维前缀和 容斥涉及304这类题型。如果题目还要求动态修改矩阵元素那就升级为二维树状数组或线段树但那是另一个专题的内容了。回看这三个模型你会发现它们没有一个是靠死记硬背解决的。前缀和的本质是“用空间换时间”把区间信息压缩到O(1)可查的状态。而哈希表和树状数组本质上是在回答“这个O(1)状态怎么快速维护”的问题。想通了这一点以后碰到“连续子数组”“区间和”“动态修改”这几个关键词你自然就知道该往哪个方向走。我个人刷这三类题时还有一个习惯先把暴力版本写出来准备一个生成随机小数组的本地测试环境然后用优化版本和暴力版本对拍。因为前缀和题目逻辑虽然不难但索引错位、初始化遗漏这类问题非常隐蔽样例全过但WA的情况太常见了。对拍能让你在几分钟内定位到到底是哪一步的边界出了错比对着题目干瞪眼高效得多。下一篇文章如果继续写这个系列我会重点讲前缀和在“区间计数”上的高级玩法——也就是配合二分查找处理第K个前缀和、利用归并排序统计前缀和的差值数量这类题目。这两类题在LeetCode周赛里经常出现一旦吃透你的前缀和就真正从“会做题”升级成“会解题”了。