02.2.1.3 前缀和与差分
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.2 数组、字符串与哈希 / 02.2.1 数组与双指针滑窗
02.2.1.3-001 一维前缀和是什么?区间和怎么查?
一句话结论
前缀和 pre[i] 为前 i 个元素之和,区间 [l, r] 的和 = pre[r+1] - pre[l];预处理 O(n),每次查询 O(1)。
概念解释
- pre[0]=0,pre[i]=a[0]+…+a[i-1]。
- 长度 n+1,避免下标错位。
- 静态数组多次查询时收益最大。
原理流程
- 遍历累加构造 pre。
- 查询时两端做差。
- 下标按 pre 的定义对齐。
代码 / 示例
int[] pre = new int[n + 1];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
int rangeSum(int l, int r) {
return pre[r + 1] - pre[l];
}
常见误区
- 误区:pre 长度 n;正解:n+1 才能表示从下标 0 开始的区间。
- 误区:区间和写
pre[r]-pre[l];正解:右端对应 pre[r+1]。
追问
- Q:一次查询值得建前缀和吗? A:不值得,直接扫 O(n) 即可;多次查询才摊薄预处理。
- Q:含负数前缀和还能用吗? A:区间求和不受影响,只是 pre 不单调。
02.2.1.3-002 前缀和的下标口径有哪些容易错?
一句话结论
统一使用 pre[0]=0、pre[i]=前 i 项和 的口径;区间 [l,r] 对应 pre[r+1]-pre[l];换口径时全文一致,避免差一位。
概念解释
- 两种常见口径:前 i 项 vs 含 a[i]。
- 选错口径会整体错位。
- 先画小例子核对。
原理流程
- 选定口径并写清定义。
- 用长度 2 的小数组验证。
- 查询公式配套使用。
代码 / 图示
a = [a0, a1, a2]
pre = [0, a0, a0+a1, a0+a1+a2]
[1,2] 和 = pre[3] - pre[1] = a1+a2
常见误区
- 误区:l、r 直接当 pre 下标;正解:右端要 +1。
- 误区:边界区间 [0, r] 漏减 pre[0];正解:pre[0]=0 天然处理。
追问
- Q:题目给闭区间还是半开区间? A:按题面转换,公式随之调整。
- Q:二维前缀和下标同理吗? A:同理,多一层边角容斥。
02.2.1.3-003 和为 K 的连续子数组个数(LC 560)怎么做?
一句话结论
扫描时维护当前前缀和 sum,用哈希记录各前缀和出现次数;sum - K 出现过的次数即以前缀 i 结尾的合法子数组数;O(n) 时间 O(n) 空间。
概念解释
- 子数组和 = pre[r+1] - pre[l] = K。
- 等价于历史前缀和等于
sum - K。 - 允许负数,前缀和不单调,不能用二分。
原理流程
- 哈希预置
{0: 1}。 - 逐个累加 sum。
- 累加
sum-K的历史次数。 - 登记当前 sum。
代码 / 示例
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
cnt.put(0, 1);
int sum = 0, ans = 0;
for (int x : nums) {
sum += x;
ans += cnt.getOrDefault(sum - k, 0);
cnt.merge(sum, 1, Integer::sum);
}
return ans;
}
常见误区
- 误区:不预置前缀和 0;正解:漏掉从下标 0 开始的子数组。
- 误区:先登记 sum 再查
sum-K;正解:先查历史再登记,避免同元素自配。
追问
- Q:数组含负数还适用吗? A:适用,前缀和哈希不要求单调。
- Q:要求子数组长度下限? A:用下标信息记录最早/合法位置再过滤。
02.2.1.3-004 为什么前缀和加哈希能处理负数?
一句话结论
哈希按值精确记录历史前缀和出现次数,不依赖前缀和大小顺序;负数只让 pre 上下波动,查找仍是按键等值匹配,因此不受单调性影响。
概念解释
- 二分/双指针依赖单调性。
- 哈希等值匹配无单调性要求。
- 重复前缀和按次数累计。
原理流程
- 不假设 pre 递增。
- 用哈希存每个 pre 值的次数。
- 按键
sum-K等值查询。
代码 / 图示
含负数:pre 1 → 3 → 2 → 5
哈希仍可按值找到 2 出现几次
常见误区
- 误区:前缀和含负就不能用;正解:只有依赖单调性的方法(二分)才受限。
- 误区:相同前缀和只存一次;正解:计数要累加,多个起点对应多个子数组。
追问
- Q:前缀和相同说明什么? A:两段之间的子数组和为 0。
- Q:和为 0 的子数组怎么统计? A:查
sum - 0,同口径计数。
02.2.1.3-005 除自身以外数组的乘积(LC 238)怎么做?
一句话结论
不能用除法时,前缀积数组存左侧乘积,后缀积存右侧乘积,结果 = 左积 × 右积;可优化为单前缀积数组 + 反向扫描;O(n) 时间 O(1) 额外(输出数组不计)。
概念解释
- 排除自身:左段乘积 × 右段乘积。
- 前缀积:
L[i] = a[0]…a[i-1]。 - 后缀积:
R[i] = a[i+1]…a[n-1]。
原理流程
- 从左到右算前缀积填结果数组。
- 从右到左维护右积,乘入结果。
- 边界积为 1。
代码 / 示例
public int[] productExceptSelf(int[] a) {
int n = a.length;
int[] ans = new int[n];
ans[0] = 1;
for (int i = 1; i < n; i++) ans[i] = ans[i - 1] * a[i - 1];
int right = 1;
for (int i = n - 1; i >= 0; i--) {
ans[i] *= right;
right *= a[i];
}
return ans;
}
常见误区
- 误区:先算总乘积再除 a[i];正解:含零时失效,题目要求不用除法。
- 误区:左右边界积写 0;正解:空段乘积为 1。
追问
- Q:含零怎么处理? A:左右乘积法天然正确,零两侧分段独立。
- Q:两趟扫描空间? A:结果数组除外 O(1),只用右积变量。
02.2.1.3-006 前缀和如何配合最值问题?
一句话结论
求子数组和与最值相关问题时,维护历史前缀和的最小/最大值:结合前缀和单调性或有序结构,快速找到满足条件的历史前缀;含负数时需平衡树或分情况讨论。
概念解释
- 目标:
pre[r] - pre[l]满足条件。 - 历史最值:固定 r 后取最优 l。
- 单调性可控时用变量维护最值。
原理流程
- 写出子数组和与两端前缀和关系。
- 固定右端,查历史最优前缀。
- 在线更新历史最值。
代码 / 图示
最大子数组和(Kadane 思想):
当前前缀 - 历史最小前缀 = 以当前结尾最大和
常见误区
- 误区:含负数仍只维护一个最小值;正解:按条件方向维护最小或最大。
- 误区:把当前前缀也纳入历史再比较;正解:先查再登记当前前缀。
追问
- Q:最大子数组和经典解法? A:Kadane 贪心/DP,O(n);前缀最小视角等价。
- Q:区间和不小于 K 的最难子数组? A:需有序结构维护历史前缀,属进阶题。
02.2.1.3-007 差分数组是什么?与前缀和什么关系?
一句话结论
差分 diff[i] = a[i] - a[i-1];对 diff 求前缀和即还原原数组;差分把区间批量加减转成两端点修改,是前缀和的逆运算。
概念解释
- 区间更新:只改 diff 两端。
- 还原:前缀和扫描。
- 适用多次区间更新后统一查询。
原理流程
- 由原数组构造差分。
- 区间
[l,r]加 v:diff[l]+=v,diff[r+1]-=v。 - 前缀和还原。
代码 / 示例
a: [1, 3, 7, 6]
diff:[1, 2, 4, -1]
对 diff 求前缀和 → 还原 a
常见误区
- 误区:差分直接回答区间和;正解:差分服务批量更新,查询要先还原或配合前缀和。
- 误区:diff 与 pre 混为一谈;正解:二者互为逆运算。
追问
- Q:单点修改对应差分怎么改? A:等价长度 1 的区间,diff[i]+=v、diff[i+1]-=v。
- Q:多次更新后顺序敏感吗? A:端点修改可累加,最后统一还原。
02.2.1.3-008 区间批量加减(LC 1109 航班预订)怎么做?
一句话结论
每条预订 [l,r] 加 k 转成差分两端修改,全部记录完成后前缀和还原;O(预订数 + n),避免逐区间遍历 O(n·m)。
概念解释
- 朴素:每条预订遍历区间,O(n·m)。
- 差分:每条 O(1) 端点修改。
- 最后一次还原 O(n)。
原理流程
- diff 数组长度 n+1。
- 每条记录
diff[l-1]+=k,diff[r]-=k(下标按口径转换)。 - 前缀和还原。
代码 / 示例
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] diff = new int[n + 1];
for (int[] b : bookings) {
int l = b[0] - 1, r = b[1] - 1, k = b[2];
diff[l] += k;
diff[r + 1] -= k;
}
for (int i = 1; i < n; i++) diff[i] += diff[i - 1];
return Arrays.copyOf(diff, n);
}
常见误区
- 误区:下标未按 1 基转 0 基;正解:题目编号从 1 开始,先减一。
- 误区:r+1 越界;正解:diff 多开一位,越界修改可省略。
追问
- Q:朴素法复杂度? A:每条预订遍历区间,O(n·m),差分化为 O(n+m)。
- Q:还原后还能再做区间查询吗? A:还原为普通数组后可再建前缀和。
02.2.1.3-009 拼车问题(LC 1094)差分怎么用?
一句话结论
上下车人数变化落在区间端点:[上车站, 下车站) 载客,差分两端增减;前缀和还原得每站人数,全程不超容量即可行。
概念解释
- 半开区间:到下车站即下车。
- 差分累加各站净变化。
- 逐站检查是否超载。
原理流程
- 差分记录每段载客变化。
- 前缀和求每站在乘人数。
- 任一站超容量返回 false。
代码 / 示例
public boolean carPooling(int[][] trips, int capacity) {
int[] diff = new int[1001];
for (int[] t : trips) {
diff[t[1]] += t[0];
diff[t[2]] -= t[0];
}
int cur = 0;
for (int d : diff) {
cur += d;
if (cur > capacity) return false;
}
return true;
}
常见误区
- 误区:下车站仍算载客;正解:半开区间,下车点释放座位。
- 误区:只检查上车时刻;正解:每一站在乘人数都要查。
追问
- Q:站点范围未知怎么开数组? A:按最大站点号开,或用哈希表记录端点后排序扫描。
- Q:贪心派车是另一类问题吗? A:本题只判断单车容量可行性,贪心派车属另一类问题。
02.2.1.3-010 二维前缀和怎么构造?
一句话结论
S[i][j] 表示左上角到 (i-1,j-1) 矩形和,递推 S[i][j] = a[i-1][j-1] + S[i-1][j] + S[i][j-1] - S[i-1][j-1];构造 O(mn)。
概念解释
- 容斥:上方与左方重叠区减回。
- 数组尺寸 (m+1)×(n+1),首行首列为 0。
- 查询时四角做差。
原理流程
- 开 (m+1)×(n+1)。
- 逐格按容斥递推。
- 查询矩形做四角差。
代码 / 示例
int[][] S = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
S[i][j] = a[i - 1][j - 1] + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
}
}
常见误区
- 误区:容斥符号写反;正解:重叠的左上区域被加两次,要减回一次。
- 误区:数组尺寸 m×n;正解:多一圈 0 边界方便查询。
追问
- Q:二维前缀和空间能否压缩? A:查询多则保留全表;流式按行处理另说。
- Q:矩阵动态修改怎么办? A:前缀和静态失效,需二维 Fenwick 树等结构。
02.2.1.3-011 二维矩形和查询公式是什么?
一句话结论
矩形 (r1,c1) 到 (r2,c2) 的和 = S[r2+1][c2+1] - S[r1][c2+1] - S[r2+1][c1] + S[r1][c1],两次减去后把多减的左上角加回。
概念解释
- 四个角对应容斥。
- 下标按 S 的 (i,j) 口径。
- 边界行/列 0 使公式统一。
原理流程
- 定位查询矩形四角。
- 代入容斥公式。
- 核对下标偏移。
代码 / 示例
int rectSum(int r1, int c1, int r2, int c2) {
return S[r2 + 1][c2 + 1] - S[r1][c2 + 1]
- S[r2 + 1][c1] + S[r1][c1];
}
常见误区
- 误区:忘记加回左上区域;正解:两块各减一次,重叠区被减两次需补回。
- 误区:r1、c1 未转换;正解:查询坐标先对齐 S 的口径。
追问
- Q:一维是二维的特例吗? A:是,容斥退化为两端做差。
- Q:多次查询同一矩阵? A:静态前缀和最优,O(mn) 构造后 O(1) 查询。
02.2.1.3-012 二维差分的基本思路是什么?
一句话结论
矩形 [r1,r2]×[c1,c2] 加 v,在差分数组四个角做容斥修改:D[r1][c1]+=v、D[r2+1][c1]-=v、D[r1][c2+1]-=v、D[r2+1][c2+1]+=v,最后二维前缀和还原。
概念解释
- 二维差分是二维前缀和的逆。
- 四角修改保证增量只覆盖目标矩形。
- 批量矩形更新后统一还原。
原理流程
- 对每个矩形改四个角。
- 做两次前缀和还原。
- 得到更新后的矩阵。
代码 / 图示
D[r1][c1] += v
D[r2+1][c1] -= v
D[r1][c2+1] -= v
D[r2+1][c2+1] += v
常见误区
- 误区:只改左上与右下;正解:容斥四角缺一不可。
- 误区:r2+1、c2+1 越界;正解:数组多开一行一列。
追问
- Q:二维差分适用什么题? A:多次矩形增减、最后统一查询的场景。
- Q:动态查询夹杂更新? A:差分不适用,需树状数组/线段树。
02.2.1.3-013 前缀和与滑动窗口怎么选型?
一句话结论
非负数组求区间和满足条件且可收缩,用滑动窗口 O(1) 空间;含负数、求子数组计数、需任意历史前缀匹配,用前缀和 + 哈希 O(n) 空间。
概念解释
- 窗口依赖收缩单调性。
- 前缀和不要求单调。
- 空间换取通用性。
原理流程
- 确认元素是否非负。
- 判断目标是窗口最优还是子数组计数。
- 选窗口或前缀和哈希。
代码 / 图示
非负 + 最短/最长窗口 → 滑窗 O(1) 空间
含负数 / 子数组计数 → 前缀和 + 哈希 O(n) 空间
常见误区
- 误区:前缀和能做的窗口题都用窗口;正解:含负数窗口收缩不成立。
- 误区:窗口题也建前缀和;正解:非负场景窗口空间更优。
追问
- Q:求子数组个数能用窗口吗? A:非负且固定条件可统计,但前缀和哈希更通用。
- Q:两种方法复杂度谁高? A:时间都 O(n),空间窗口更省。
02.2.1.3-014 差分相比逐区间更新赢在哪?
一句话结论
m 个区间各长度 L,逐一遍历是 O(m·L);差分每条区间 O(1) 端点修改,最后 O(n) 还原,整体 O(n+m),避免重复扫区间内元素。
概念解释
- 重复劳动:区间内每个元素被多次遍历。
- 差分:增量记在边界,还原时统一累加。
- 离线批量更新最优。
原理流程
- 确认所有更新先给齐再查询。
- 端点记录增量。
- 前缀和一次性还原。
代码 / 图示
逐区间:Σ区间长度
差分:m 次端点修改 + n 次还原
常见误区
- 误区:差分能在线响应查询;正解:差分适合离线批量,夹杂查询需还原后再查。
- 误区:区间端点修改顺序敏感;正解:增量可交换累加。
追问
- Q:区间赋值(覆盖)不是加减? A:差分只支持增量叠加,覆盖需其他结构。
- Q:还原后还能继续差分吗? A:基于还原后的数组重新构造差分。
02.2.1.3-015 前缀和累加如何防溢出?
一句话结论
先估算累加范围,选择足够宽的整型(如 long);题目给定上下界时核对是否越界;输出按题目口径转回,必要时取模。
概念解释
- int 累加可能静默溢出回绕。
- long 拓宽范围。
- 取模题需按模运算规则处理负数。
原理流程
- 估算最大前缀和量级。
- 选宽类型累加。
- 需要模运算时规范取模。
代码 / 示例
long sum = 0;
for (int x : a) sum += x; // 宽类型累加,避免 int 溢出
常见误区
- 误区:int 累加够用凭感觉;正解:按 n 与单值上界估算。
- 误区:取模后负数转正数;正解:
(x % mod + mod) % mod规范化。
追问
- Q:哈希键用前缀和溢出了怎么办? A:宽类型存储;模哈希另说。
- Q:超大数求和? A:高精度模拟,见字符串大数题。
02.2.1.3-016 前缀和题有哪些边界用例?
一句话结论
空数组、单元素、全零、全负、目标 K=0、前缀和重复出现、区间覆盖首尾;分别验证预置前缀 0 与计数累加。
概念解释
- K=0:子数组和为 0,依赖重复前缀和。
- 全零:每个前缀和都重复。
- 单元素:区间退化为单点。
原理流程
- 构造空、单元素用例。
- 构造 K=0 与全零。
- 核对计数与下标。
代码 / 图示
[] / [x] / [0,0,0] / 全负数
K = 0
前缀和多次相同
常见误区
- 误区:K=0 时忘记预置前缀和 0;正解:从起点开始的零和子数组要计入。
- 误区:全零只算一个子数组;正解:按位置组合计数。
追问
- Q:单元素等于 K? A:预置 pre[0]=1 后可被正确统计。
- Q:区间查询 l=r? A:公式返回单点值。
02.2.1.3-017 前缀和数组可以动态更新吗?
一句话结论
标准前缀和是静态结构,单点修改后需 O(n) 重建;频繁更新与查询混合时改用树状数组(Fenwick)或线段树,支持 O(log n) 单点改与区间查。
概念解释
- 静态:预处理一次,多次查询。
- 动态:更新与查询交错。
- 树状数组:差分思想的在线结构。
原理流程
- 判断是否有更新操作。
- 无更新:前缀和。
- 有更新:树状数组/线段树。
代码 / 图示
静态查询多:前缀和 O(n) 预处理 O(1) 查
动态改查:树状数组 O(log n) 改/查
常见误区
- 误区:改一个元素后手动修前缀和;正解:其后所有前缀和都受影响,整体重建。
- 误区:前缀和支持区间修改;正解:区间批量修改用差分,仍是离线口径。
追问
- Q:树状数组原理? A:利用二进制下标管理区间和,单点更新与前缀查询 O(log n)。
- Q:二维动态区间和? A:二维树状数组或线段树。
02.2.1.3-018 前缀和与原数组是什么存储关系?
一句话结论
前缀和是原数组的派生结构,额外 O(n) 空间保存累加结果;可由原数组重建,不保存独立信息;原数组修改后前缀和即失效。
概念解释
- 派生:可反推区间和。
- 冗余:以空间换查询速度。
- 一致性:原数组变则 pre 失效。
原理流程
- 读入原数组。
- 构造 pre 副本关系。
- 原数组改动后重建 pre。
代码 / 图示
原数组 a → pre 派生结构
查询:pre 做差
更新 a 后:pre 必须重建
常见误区
- 误区:pre 与 a 同步自动更新;正解:代码需显式重建。
- 误区:省空间直接在 a 上累加;正解:覆盖原数组后无法还原单点值。
追问
- Q:能否只用 pre 恢复原数组? A:可以,差分相减
a[i]=pre[i+1]-pre[i]。 - Q:输出需要原数组吗? A:需要保留原引用,别用 pre 覆盖。
02.2.1.3-019 差分还原时常见错误有哪些?
一句话结论
常见错误:r+1 越界未截断、还原方向写反、区间端点口径不一致、忘记最后做前缀和;编码前先在长度 3 的小数组上手算一遍。
概念解释
- 越界:右端后一位可能出界。
- 方向:还原是从前向后累加。
- 口径:1 基与 0 基统一。
原理流程
- 确认区间端点口径。
- 端点修改留越界位。
- 从前向后前缀和还原。
代码 / 图示
diff[r+1] 越界时省略
还原:diff[i] += diff[i-1]
常见误区
- 误区:从后向前还原;正解:差分还原是从前向后累加。
- 误区:端点修改后直接当原数组;正解:必须前缀和还原。
追问
- Q:多个区间叠加后顺序? A:端点增量可任意顺序累加。
- Q:还原后负数值正常吗? A:原数组允许负则正常,否则检查端点符号。
02.2.1.3-020 前缀和/差分题如何汇报复杂度?
一句话结论
前缀和:构造 O(n)、查询 O(1)、空间 O(n);差分:修改 O(1)/区间、还原 O(n)、空间 O(n);二维对应 O(mn);汇报时分预处理与查询两段。
概念解释
- 预处理代价不可省略。
- 查询代价按单次口径。
- 空间为派生数组大小。
原理流程
- 标注构造/还原复杂度。
- 标注单次查询复杂度。
- 说明辅助空间。
代码 / 图示
一维前缀和:预处理 O(n),查询 O(1),空间 O(n)
差 分 :修改 O(1),还原 O(n),空间 O(n)
二维前缀和:构造 O(mn),查询 O(1)
常见误区
- 误区:只说 O(1) 查询不提预处理;正解:要把构造 O(n) 一并说明。
- 误区:差分空间 O(1);正解:diff 数组 O(n)。
追问
- Q:一次查询还用前缀和吗? A:预处理 O(n) 不划算,直接扫描。
- Q:m 次查询总复杂度? A:O(n + m),每次 O(1)。