前缀和
前缀和预先保存从起点到每个位置的累计值，把静态区间求和变成两次前缀值相减。本文使用左闭右开的区间，前缀数组比原数组多一个元素。
1. 面试核心
先记住这几条，再读正文- prefix[0]=0，prefix[i+1]=prefix[i]+a[i]。
- 区间 [l,r) 的和为 prefix[r]−prefix[l]，单次查询 O(1)。
- 预处理时间和空间均为 O(n)；频繁修改时需要考虑其他结构。
2. 共同前缀抵消
prefix[r] 包含下标 0 到 r−1，prefix[l] 包含下标 0 到 l−1，相减后恰好剩下 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) 的和是 5-2=3，空区间 [2,2) 为 0。long 降低累计 int 数据时溢出的风险，仍需根据最大输入规模检查 long 是否足够。
3. 子数组和与哈希计数
如果某个区间和为 k，就有 prefix[r]-prefix[l]=k。扫描右端 r 时，可在哈希表中查找之前出现过多少个 prefix[r]-k。
初始记录前缀 0 出现一次，用来覆盖从下标 0 开始的区间。每步先查计数再加入当前前缀，避免把空区间算进去。重复前缀必须保存次数，不能只保存是否存在。负数不会破坏这个等式，因此这种方法能处理不满足滑动窗口单调性的输入。
4. 使用边界
普通前缀和适合数据固定、查询频繁的情况。修改一个位置会影响其后的全部前缀，最坏更新成本 O(n)。若更新和查询都多，可以按岗位需要学习树状数组或线段树。
区间最大值通常不能靠两个前缀最大值相减求出，因为 max 没有对应的逆操作。练习可使用现有304. 二维区域和检索 - 矩阵不可变，先写出一维公式，再推导二维容斥。
5 · 面试题卡片
先想答案，再翻面题目来自公开面经。点任意一张进入翻卡，可左右切换，看完回到这里。
逐张翻看 1 张 →5.1 有负数时，求和为 k 的子数组数量如何使用前缀和？
出现公司：暂无已核验的公开来源（本站自测）
考察重点：前缀差等式、哈希计数初始化与负数、重复前缀的影响。
参考回答
把问题改写为查找此前等于当前前缀减 k 的前缀个数。用哈希表维护次数，初始化 0 的次数为 1，每步先查询后记录当前前缀，便能统计非空区间。期望时间 O(n)、空间 O(n)，不依赖元素非负；答案本身可能达到平方级，计数类型也需要足够大。