1. 什么时候值得预处理
已知数组不再变化,但需要多次询问某个连续区间的元素和。每次直接扫描区间,单次最坏为 O(n),q 次查询最坏为 O(qn)。
前缀和用一次扫描保存中间结果,将单次区间查询降为常数成本;代价是额外空间。只查询一次时,直接求和通常已经足够。
本篇对应学习路线第 04 周,先修是数组扫描;最后的计数变式还需要数组与哈希。示例使用安全整数,所有累计和、区间和及差值也应位于安全整数范围内;不涵盖浮点精度或大整数计算。
2. 用一个多出来的位置统一边界
定义 prefix[i] 表示原数组前 i 个元素之和,即区间 [0, i)。长度为 n 的数组对应长度为 n + 1 的前缀数组,其中 prefix[0] = 0。
function buildPrefix(nums) {
const prefix = [0];
for (const value of nums) {
prefix.push(prefix[prefix.length - 1] + value);
}
return prefix;
}例如数组 [2, -1, 3] 对应 [0, 2, 1, 4]。负数不会破坏前缀和公式,前缀值也不需要保持递增。
构建时间为 O(n),返回数组占用 O(n) 空间,除此之外只需要常数辅助空间;不修改输入。
3. 区间查询为什么可以相减
3.1 统一使用左闭右开区间
本篇的查询区间为 [left, right),含左端、不含右端,与前缀定义一致。它不同于二分文章的候选闭区间;不同算法可以使用不同约定,但同一实现内部必须一致。
prefix[right] 包含 [0, right),减掉 prefix[left] 包含的 [0, left),剩下的正是目标区间。空区间 left === right 的和为零。
function rangeSum(prefix, left, right) {
if (!Number.isInteger(left) || !Number.isInteger(right) ||
left < 0 || right < left || right >= prefix.length) {
throw new RangeError('Expected 0 <= left <= right <= input length');
}
return prefix[right] - prefix[left];
}此函数要求 prefix 是 buildPrefix 的结果,检查查询端点是否合法;非法端点抛错,不默默返回 NaN。原数组长度为 n 时允许 right === n,因为前缀数组长度为 n + 1。
单次查询时间为 O(1),额外辅助空间为 O(1)。先构建、再做 q 次查询,总时间为 O(n + q),保存前缀的空间为 O(n)。
3.2 手推与边界
| 原数组 | 查询区间 | 期望结果 | 检查目的 |
|---|---|---|---|
[2, -1, 3] | [0, 3) | 4 | 整段 |
[2, -1, 3] | [1, 3) | 2 | 相减去掉前缀 |
[2, -1, 3] | [1, 2) | -1 | 单元素及负数 |
[2, -1, 3] | [2, 2) | 0 | 空区间 |
[] | [0, 0) | 0 | 空输入仍有前缀零 |
如果题目给出闭区间 [left, right],需要转换成 prefix[right + 1] - prefix[left]。先画出区间再写公式,不要背一个脱离端点约定的减法。
原数组更新后,旧前缀和不会自动刷新。第一轮可重新构建;频繁更新与查询混合时,才考虑其他数据结构。
4. 选学:连续子数组的和等于目标
4.1 把区间枚举改为查找旧前缀
这部分是第 04 周的选学内容,可以等基础查询熟练后再做。目标是统计和为 target 的非空连续子数组数量,允许负数和零,不改变输入。
朴素解法固定左端点,向右累计和并检查,时间为 O(n²)。根据前缀关系:若当前右端的前缀为 sum,需要找到之前满足 oldPrefix = sum - target 的前缀。
同一个前缀可能出现多次,每次出现代表不同的左端点,因此表中要保存次数,不能只用集合。
function countSubarrays(nums, target) {
const frequencies = new Map([[0, 1]]);
let sum = 0;
let count = 0;
for (const value of nums) {
sum += value;
count += frequencies.get(sum - target) ?? 0;
frequencies.set(sum, (frequencies.get(sum) ?? 0) + 1);
}
return count;
}平均时间为 O(n),辅助空间为 O(n),按哈希操作的平均常数成本模型计算。输入规模还需保证答案计数不超过安全整数范围。
4.2 三个最容易漏掉的条件
0的初始次数为1,代表还没读取元素时的空前缀,使从下标零开始的区间也能被统计。它不代表把空子数组算作答案。- 先查询、再保存当前前缀,保证只匹配更早的左端点。否则目标为零时可能把空区间算进去。
- 保存次数而不只保存存在性:
[0, 0]、目标为0时,有两个长度为一的区间和一个长度为二的区间,共3个答案。
[1, -1, 1]、目标为 1 的答案也是 3。不要把正数区间求和的滑窗策略直接搬到这里:负数使扩张和缩小不再保证区间和单调变化。
5. 自己验证并说明适用范围
先独立完成基本构建和查询,再选做计数变式。验证空数组、负数、全零、首尾区间、非法端点和输入不变。
node --test tests/algorithm-linear-examples.test.mjs测试用小数组的直接枚举结果对照优化实现,尤其检查零和重复前缀,不只检查一个正常样例。
练习:对数组 [3, -2, 5, 1] 手写前缀表,求 [1, 4) 的和,然后修改第一个元素,说明哪些前缀会变化。闭卷追问:为什么前缀数组比原数组多一个元素?
会推导后即可继续学习路线的链表阶段;二维前缀和与动态区间结构留待后续按需学习;批量区间更新可继续选读下一节。
6. 选学:差分用于批量区间更新
前缀和将多次区间查询变成相减;差分反过来,将多次区间加值变成端点标记,最后一次还原。它适合“全部更新结束后才读取最终结果”,不直接支持每次更新后立刻查询区间和。
定义相邻差值:首项是原数组首项,后续是当前值减去前一项。给 [left, right) 全部增加 delta 时,只需在左端增加 delta,在右端减去 delta;前缀累加就能还原结果。
function applyRangeAdds(nums, updates) {
const diff = new Array(nums.length + 1).fill(0);
for (let i = 0; i < nums.length; i++) {
diff[i] = nums[i] - (i === 0 ? 0 : nums[i - 1]);
}
for (const [left, right, delta] of updates) {
if (!Number.isInteger(left) || !Number.isInteger(right) ||
left < 0 || right < left || right > nums.length) {
throw new RangeError('Expected 0 <= left <= right <= input length');
}
diff[left] += delta;
diff[right] -= delta;
}
const result = [];
let value = 0;
for (let i = 0; i < nums.length; i++) {
value += diff[i];
result.push(value);
}
return result;
}约定每次更新是三元组 [left, right, delta],数组元素、增量及所有中间运算均在安全整数范围内。不修改原数组或更新列表;空区间的两个标记抵消。末尾多一个哨兵位置,允许 right 等于数组长度。
长度为 n、更新数为 q 时,时间为 O(n + q),差分辅助数组与结果各占 O(n)。相比每次遍历区间的最坏 O(nq),省下的是重复更新的工作。
例如 [1, 2, 3],先给 [0, 2) 加 2,再给 [1, 3) 减 1,结果为 [3, 3, 2]。验证重叠更新、负增量、空区间和整个数组,先用直接循环更新作对照。此节不要求在第 04 周与所有前缀和变式一起掌握。
评论
正在加载评论…