前缀和
前缀和保存累计值，用前缀差计算静态区间和。本文负责一维求和、子数组计数、二维容斥和差分。
1. 面试核心
先记住这几条，再读正文- 前缀定义。
prefix[i]保存前 i 项的和，满足prefix[0]=0、prefix[i+1]=prefix[i]+a[i]。 - 区间查询。 区间
[l,r)的和为prefix[r]-prefix[l]，查询为 O(1)。 - 目标和计数。 前缀和配合哈希频次，可统计含负数的目标和子数组。当前前缀为 s 时，查找此前出现过多少个 s−k，即得到以当前位置结尾、和为 k 的子数组数。卡 · 子数组和与哈希计数
- 二维区域和。 二维区域和从右下角的前缀和中减去上方、左方区域，再补回被重复减去的左上角区域。卡 · 二维前缀和与容斥
2. 共同前缀抵消
prefix[r] 累加下标 0 到 r−1。减去 prefix[l] 后，留下 l 到 r−1。
static long[] prefix(int[] a) {
long[] sums = new long[a.length + 1];
for (int i = 0; i < a.length; i++) {
sums[i + 1] = sums[i] + a[i];
}
return sums;
}
输入 [2,-1,4] 得到 [0,2,1,5]。区间 [1,3) 的和为 3，空区间的和为 0。Java int 数组的完整累加可由 long 容纳。表达式再减去外部 long 目标时，仍需核对目标范围。
3. 子数组和与哈希计数
目标和 k 满足 prefix[r]-prefix[l]=k。扫描 r 时，查询此前 prefix[r]-k 出现的次数。
初始化 count[0]=1，覆盖从首项开始的区间。每步先查询，再记录当前前缀。这个顺序避免 k=0 时把空区间算入答案。重复前缀需保存次数，负数也满足相同等式。
输入 [0,0]、k=0，第一步计入 1，第二步计入 2。答案为 3。n 项共有 n*(n+1)/2 个非空子数组，答案计数应使用 long。
4. 二维前缀和与容斥
定义 P[r][c] 为前 r 行、前 c 列的总和。第 0 行与第 0 列初始化为 0。
P[r+1][c+1] = a[r][c] + P[r][c+1] + P[r+1][c] - P[r][c]
sum([r1,r2), [c1,c2)) = P[r2][c2] - P[r1][c2]
- P[r2][c1] + P[r1][c1]
左上角同时被两个前缀减去，所以需加回一次。m×n 矩阵预处理为 O(mn)，查询为 O(1)。矩阵总和与中间表达式都需核对数值上界。
4.1 差分与区间增加
定义 d[0]=a[0]，后续 d[i]=a[i]-a[i-1]。为 [l,r) 增加 v，只需 d[l]+=v、d[r]-=v。长度 n+1 的差分数组可容纳右侧哨兵。最后累加差分，即可恢复每项新值。
差分适合批量修改后统一取结果。单次标记 O(1)，最终恢复 O(n)。
5. 使用边界
普通前缀和更新一项会影响后缀，最坏需 O(n)。频繁更新并查询时，可考虑树状数组或线段树。
区间最大值缺少前缀相减的逆操作。相关练习见304. 二维区域和检索 - 矩阵不可变。
6 · 面试题卡片
本页题目与参考回答
6.1 含负数时如何统计和为 k 的子数组？
考察重点：前缀差、频次和查询顺序。
相关内容：子数组和与哈希计数。
参考回答
统计此前等于当前前缀减 k 的前缀个数即可。
初始化 0 出现一次，每步先查后记。负数仍满足前缀差等式。哈希分布良好时，期望时间 O(n)，空间 O(n)。
6.2 二维区域和为何要补回左上角？
考察重点：前缀区域与重叠部分。
参考回答
左上角同时属于上方与左方区域，被减去了两次。
补回一次后，目标矩形之外的项恰好抵消。第 0 行、第 0 列设为 0，可统一贴边矩形的公式。
6.3 差分如何将一次区间增加变为 O(1) 标记？
考察重点：端点增量与最终恢复。
相关内容：差分与区间增加。
参考回答
对半开区间 [l,r) 增加 v，只需执行 d[l] += v 和 d[r] -= v。
对差分数组 d 求前缀和时，增量从 l 开始生效，到 r 抵消，因此单次区间更新只需 O(1) 标记。批量标记后统一恢复数组，恢复时间为 O(n)。