Skip to content

1. 什么时候值得预处理 ​

已知数组不再变化,但需要多次询问某个连续区间的元素和。每次直接扫描区间,单次最坏为 O(n),q 次查询最坏为 O(qn)。

前缀和用一次扫描保存中间结果,将单次区间查询降为常数成本;代价是额外空间。只查询一次时,直接求和通常已经足够。

本篇对应学习路线第 04 周,先修是数组扫描;最后的计数变式还需要数组与哈希。示例使用安全整数,所有累计和、区间和及差值也应位于安全整数范围内;不涵盖浮点精度或大整数计算。

2. 用一个多出来的位置统一边界 ​

定义 prefix[i] 表示原数组前 i 个元素之和,即区间 [0, i)。长度为 n 的数组对应长度为 n + 1 的前缀数组,其中 prefix[0] = 0。

js
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 的和为零。

js
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 的前缀。

同一个前缀可能出现多次,每次出现代表不同的左端点,因此表中要保存次数,不能只用集合。

js
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 三个最容易漏掉的条件 ​

  1. 0 的初始次数为 1,代表还没读取元素时的空前缀,使从下标零开始的区间也能被统计。它不代表把空子数组算作答案。
  2. 先查询、再保存当前前缀,保证只匹配更早的左端点。否则目标为零时可能把空区间算进去。
  3. 保存次数而不只保存存在性:[0, 0]、目标为 0 时,有两个长度为一的区间和一个长度为二的区间,共 3 个答案。

[1, -1, 1]、目标为 1 的答案也是 3。不要把正数区间求和的滑窗策略直接搬到这里:负数使扩张和缩小不再保证区间和单调变化。

5. 自己验证并说明适用范围 ​

先独立完成基本构建和查询,再选做计数变式。验证空数组、负数、全零、首尾区间、非法端点和输入不变。

sh
node --test tests/algorithm-linear-examples.test.mjs

测试用小数组的直接枚举结果对照优化实现,尤其检查零和重复前缀,不只检查一个正常样例。

练习:对数组 [3, -2, 5, 1] 手写前缀表,求 [1, 4) 的和,然后修改第一个元素,说明哪些前缀会变化。闭卷追问:为什么前缀数组比原数组多一个元素?

会推导后即可继续学习路线的链表阶段;二维前缀和与动态区间结构留待后续按需学习;批量区间更新可继续选读下一节。

6. 选学:差分用于批量区间更新 ​

前缀和将多次区间查询变成相减;差分反过来,将多次区间加值变成端点标记,最后一次还原。它适合“全部更新结束后才读取最终结果”,不直接支持每次更新后立刻查询区间和。

定义相邻差值:首项是原数组首项,后续是当前值减去前一项。给 [left, right) 全部增加 delta 时,只需在左端增加 delta,在右端减去 delta;前缀累加就能还原结果。

js
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 周与所有前缀和变式一起掌握。

评论

正在加载评论…