企业官网建设流程全解析

刷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(vector<int>& nums, int k) { unordered_map<long 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 ans

2.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) % K

sum % K + K先把负数补成(负数+K)的正值，再对K取一次模，这样无论sum是正还是负，都能得到[0, K-1]范围内的结果。这是这类整除题目通用的写法，建议直接当成肌肉记忆。

满分的实现：

class Solution { public: int subarraysDivByK(vector<int>& nums, int k) { unordered_map<int, 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 三题对比：什么时候查次数，什么时候查下标

如果你仔细看这三道题，会发现它们共用同一个骨架，但细节差异决定了“存什么、怎么查”：

区别清晰了：题目问“有几个”，哈希表存次数；题目问“最长”，哈希表存首次下标。存次数的题里，当前遍历到的位置可以重复与多个历史位置配对，所以每个前缀和出现次数都要累加；存下标的题里，取最远的历史位置就够了，所以只存首次出现。这个判断在面试时能帮你快速定位解法方向。

3. 二维前缀和实战与树状数组扩展

3.1 LeetCode 304：二维区域和检索

题目要求设计一个类，初始化时传入矩阵，之后反复调用sumRegion(r1, c1, r2, c2)查询子矩阵和。如果每次都暴力累加，一次查询O(n²)，多个查询一起到来时性能很差。二维前缀和把每次查询压到O(1)。

我的实现习惯是让前缀和矩阵pref比原矩阵大一圈，即pref.size() = n+1，pref[0].size() = m+1，所有下标从1开始。这样做的好处是不用单独判断r1-1或c1-1是否为负数——它们天然对应0行/0列，值本来就是0。

class NumMatrix { private: vector<vector<int>> pref; public: NumMatrix(vector<vector<int>>& matrix) { int n = matrix.size(), m = matrix[0].size(); pref.assign(n + 1, vector<int>(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) = 1（0011与1101按位与得0001，值1）
• lowbit(4) = 4（0100与1100按位与得0100，值4）
• lowbit(6) = 2（0110与1010按位与得0010，值2）
• lowbit(8) = 8（1000与1000按位与得1000，值8）

tree[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]），然后去掉最低位的1：11 - lowbit(11) = 11 - 1 = 10，再取tree[10]（管理[9,10]），再去掉最低位的1：10 - lowbit(10) = 10 - 2 = 8，再取tree[8]（管理[1,8]），下一步8 - lowbit(8) = 0，结束。所以：

sum(11) = tree[11] + tree[10] + tree[8]

观察这三个下标：11（1011）、10（1010）、8（1000），每一步都在把最低位的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 的二进制是0011，lowbit = 1，更新tree[3]，下一步3 + 1 = 4
• 4 的二进制是0100，lowbit = 4，更新tree[4]，下一步4 + 4 = 8
• 8 的二进制是1000，lowbit = 8，更新tree[8]，下一步8 + 8 = 16
• 16 的二进制是10000，lowbit = 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 { vector<int> 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)时分配n+1个元素，tree[0]不用。查询时如果传入下标0，函数应该直接返回0；修改时如果idx = 0，idx & -idx也是0，会导致死循环。所以在封装函数里，对idx <= 0的情况做保护，或者调用方保证下标至少从1开始。我在处理LeetCode题目时，习惯把0-based下标统一+1后再传给树状数组，这样所有边界逻辑都归于“1..n”的标准区间。

4.6 总结一份自查表

5. 专题二的核心套路复盘：先判断题目类型

写到这里，我想把这些零散的知识点重新串联一下。前缀和进阶题其实就三种模型，面试时拿到题可以先对号入座。

第一种是连续子数组的“个数”问题，典型特征是问“有多少个子数组满足某个条件”。解题框架是前缀和 + 哈希计数，核心是把条件pref[j] - pref[i] == target改写成pref[i] == pref[j] - target，用哈希表查历史次数。560、974都属于这一类，区别只是等式右边换成了取模后的值。

第二种是连续子数组的“最长长度”问题，典型特征是问“最长的满足条件的连续子数组有多长”。解题框架是前缀和 + 哈希记录首次下标，因为最长一定对应最早出现的位置。525和“和为零的最长子数组”都是这个套路。

第三种是矩阵区域查询问题，典型特征是在二维矩阵中多次查询任意矩形区域的和。解题框架是二维前缀和 + 容斥，涉及304这类题型。如果题目还要求动态修改矩阵元素，那就升级为二维树状数组或线段树，但那是另一个专题的内容了。

回看这三个模型，你会发现它们没有一个是靠死记硬背解决的。前缀和的本质是“用空间换时间”，把区间信息压缩到O(1)可查的状态。而哈希表和树状数组，本质上是在回答“这个O(1)状态怎么快速维护”的问题。想通了这一点，以后碰到“连续子数组”“区间和”“动态修改”这几个关键词，你自然就知道该往哪个方向走。

我个人刷这三类题时还有一个习惯：先把暴力版本写出来准备一个生成随机小数组的本地测试环境，然后用优化版本和暴力版本对拍。因为前缀和题目逻辑虽然不难，但索引错位、初始化遗漏这类问题非常隐蔽，样例全过但WA的情况太常见了。对拍能让你在几分钟内定位到到底是哪一步的边界出了错，比对着题目干瞪眼高效得多。

下一篇文章如果继续写这个系列，我会重点讲前缀和在“区间计数”上的高级玩法——也就是配合二分查找处理第K个前缀和、利用归并排序统计前缀和的差值数量这类题目。这两类题在LeetCode周赛里经常出现，一旦吃透，你的前缀和就真正从“会做题”升级成“会解题”了。