前缀和与差分

讲解

前缀和是一个预处理思想：先算好 prefix[i] = 前 i 个元素之和，之后任意区间 [l, r] 的和用 prefix[r+1] - prefix[l] 一次减法得到。预处理 O(n)、每次查询 O(1)——把「反复区间求和」从每次 O(n) 压到 O(1)，代价只是 O(n) 的额外数组。prefix[0] = 0 这个「空前缀」是关键的边界设计：它让 l = 0 的查询也用同一个公式，无需特判。

前缀和 + 哈希表的组合拳能解一大类「子数组和」问题。以「和为 K 的子数组个数」为例：遍历到位置 i 时，累加和为 sum；如果之前某个位置的累加和是 sum - k，那么那两个位置之间的子数组和就是 k。用 Map 记录每个累加和出现的次数，一遍扫过即得答案，O(n) 解决 O(n²) 的枚举。注意先查后存、且初始放入 {0: 1}（空前缀）——否则从数组开头算起的合法子数组会被漏掉。

差分是前缀和的逆运算，专治「区间批量加法」：要对 [l, r] 每个元素加 c，只需 diff[l] += c、diff[r+1] -= c，O(1) 完成一次区间更新；所有更新做完后对 diff 求前缀和即还原出最终数组。与原始做法（每次更新扫一遍区间）相比，m 次更新从 O(m·n) 降到 O(m + n)。这对「互逆」的兄弟——前缀和把区间查询变 O(1)，差分把区间修改变 O(1)——放一起记最牢。

示例

区间和查询（NumArray）、和为 K 的子数组个数（前缀和 + 哈希）、差分数组区间批量加法：

import assert from 'node:assert/strict';

class NumArray {
  constructor(nums) {
    this.prefix = [0]; // prefix[0] = 0 是空前缀
    for (const x of nums) {
      this.prefix.push(this.prefix[this.prefix.length - 1] + x);
    }
  }
  sumRange(left, right) {
    return this.prefix[right + 1] - this.prefix[left];
  }
}

function subarraySum(nums, k) {
  const countOf = new Map([[0, 1]]); // 空前缀：累加和 0 出现 1 次
  let sum = 0;
  let count = 0;
  for (const x of nums) {
    sum += x;
    count += countOf.get(sum - k) ?? 0; // 先查：之前有多少个 sum-k
    countOf.set(sum, (countOf.get(sum) ?? 0) + 1); // 后存
  }
  return count;
}

// 差分：m 次区间加法 O(1) 一次，最后一次前缀和还原
function applyRangeAdds(length, updates) {
  const diff = new Array(length).fill(0);
  for (const [start, end, inc] of updates) {
    diff[start] += inc;
    if (end + 1 < length) diff[end + 1] -= inc;
  }
  const result = [];
  let cur = 0;
  for (const d of diff) {
    cur += d;
    result.push(cur);
  }
  return result;
}

const na = new NumArray([-2, 0, 3, -5, 2, -1]);
assert.strictEqual(na.sumRange(0, 2), 1);
assert.strictEqual(na.sumRange(2, 5), -1);
assert.strictEqual(na.sumRange(0, 5), -3);

assert.strictEqual(subarraySum([1, 1, 1], 2), 2);
assert.strictEqual(subarraySum([1, 2, 3], 3), 2);
assert.strictEqual(subarraySum([1, -1, 0], 0), 3); // 有 0 和负数，滑动窗口失效的场景

assert.deepStrictEqual(applyRangeAdds(5, [[1, 3, 2], [2, 4, 3], [0, 2, -2]]), [-2, 0, 3, 5, 3]);

console.log('前缀和与差分示例全部通过');

subarraySum 的第三个断言值得玩味：数组含负数时累加和不再单调，滑动窗口套路失效，前缀和 + 哈希却能照常工作——这正是「识别模式适用边界」的实战案例。

常见坑

• prefix 的下标错位：prefix[i] 是前 i 个元素的和（不含 nums[i]），区间 [l, r] 用 prefix[r+1] - prefix[l]；定义成「含」或「不含」都可以，但全篇必须统一。
• subarraySum 忘记放入 {0: 1}：从位置 0 开始的合法子数组依赖空前缀，漏了它会少算。
• 先存后查：和两数之和同理，先存再查会把「长度 0 的子数组」也算进去（自己配自己），顺序不能反。
• 差分忘记右端点后一位减回去：diff[end + 1] -= inc 是让增量「止于区间右端」，漏了增量会一路加到数组尾。
• 区间修改一次就还原一次：差分的优势在「批量修改、一次还原」；每次修改都要查结果的场景该换树状数组/线段树（进阶话题）。

小结

前缀和：预处理 O(n)，区间查询 O(1)；配哈希表解子数组和家族；差分是其逆运算，区间修改 O(1)、一次还原。下一章进入算法面试的最大山头：动态规划入门。