数组基础与常用操作

前缀和技巧

它解决的是「反复查询区间和」

给一个不变的数组，反复问「第 i 到第 j 个元素的和是多少」。 每次现算是 O(n)，问 q 次就是 O(nq)。

前缀和用一次 O(n) 预处理把每次查询降到 O(1)。

⚠️ 先说个反直觉的：查询次数太少时它更慢

「O(1) 查询」听着无敌，但预处理那一趟 O(n) 是先付的。查询次数不够多， 这笔钱就白花了。实测（n = 200000，每次查询覆盖半个数组，重复 7 次取中位数）：

查询次数 q 暴力 前缀和（含预处理） 谁快
1 0.51 ms 0.61 ms 暴力 1.20×
2 0.17 ms 0.42 ms 暴力 2.50×
4 0.32 ms 0.44 ms 暴力 1.38×
5 0.41 ms 0.55 ms 暴力 1.36×
8 0.64 ms 0.55 ms 前缀和 1.17×（交叉点）
16 1.30 ms 0.46 ms 前缀和 2.81×
64 5.25 ms 0.62 ms 前缀和 8.48×

⭐ 交叉点在 q ≈ 8。低于它，老老实实累加更快。 📌 这不影响面试答题（面试问的是「反复查询」，q 很大）， 但它提醒一件事：「优化成 O(1)」要问「摊在多少次查询上」。 和单调栈、二分 那两篇是同一个教训。

一维：定义要多一位

function buildPrefix(nums) {
  // preSum[i] = nums 前 i 个元素的和（不含 nums[i]）
  const preSum = new Array(nums.length + 1).fill(0);   // 🚨 长度 n+1
  for (let i = 0; i < nums.length; i++) {
    preSum[i + 1] = preSum[i] + nums[i];
  }
  return preSum;
}

// 闭区间 [i, j] 的和
const rangeSum = (preSum, i, j) => preSum[j + 1] - preSum[i];

nums = [3,1,4,1,5] 对应 preSum = [0,3,4,8,9,14]。 求 [1,3] 的和：preSum[4] - preSum[1] = 9 - 3 = 6，即 1+4+1。✓

🚨 那多出来的一位不是凑数

preSum[0] = 0 表示「前 0 个元素的和」。有了它，rangeSum 才能是一行。

如果按「preSum[i] = 前 i+1 个元素的和」来定义（长度 n），公式就得写成：

const rangeSumNoPad = (p, i, j) => (i === 0 ? p[j] : p[j] - p[i - 1]);
//                                  ↑ 多出来的分支

⭐ 多开一位，换掉一个 if。 这是个反复出现的模式 —— LCS 的 dp 数组开 m+1 行是同一个道理： 让「什么都不取」成为一个合法的、值恰好为零的状态，边界就自动成立了。

⚠️ 漏掉那个 i === 0 分支的症状：只有查询从下标 0 开始的区间时才错， 而且错成 p[j] - p[-1] = p[j] - undefined = NaN。

实测 nums = [3,1,4,1,5]：

查 [0,3]    漏分支得 NaN，正确值 9
查 i > 0 的全部区间    逐一比对，全部不受影响
0 + NaN + 100 = NaN    一旦产生就污染后续所有算术

⭐ 这个 bug 的形状值得记：它不是「算错」，是「只在一类输入上算错」。 如果测试用例恰好都不从下标 0 起算，它可以一直潜伏。

二维：容斥原理

function build2D(matrix) {
  const m = matrix.length, n = matrix[0].length;
  // pre[i][j] = 左上角 (0,0) 到 (i-1,j-1) 这个矩形的和
  const pre = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      pre[i][j] = matrix[i - 1][j - 1]
        + pre[i - 1][j]        // 上面那块
        + pre[i][j - 1]        // 左边那块
        - pre[i - 1][j - 1];   // 🚨 左上角被加了两次，减回来
    }
  }
  return pre;
}

// 矩形 (r1,c1) 到 (r2,c2)（都是闭区间）的和
const rect = (pre, r1, c1, r2, c2) =>
  pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1];

⭐ 两处的 - pre[i-1][j-1] 和 + pre[r1][c1] 都是容斥： 加了两遍的那块要减掉一次，减了两遍的那块要加回来一次。 画个田字格数一下每块被算了几次，比背公式牢。

🚨 漏掉容斥项的症状：两处漏法完全相反

容斥项有两处（建表时的 - pre[i-1][j-1]、查询时的 + pre[r1][c1]）， 而流传的说法「症状是结果偏大，且第一行第一列恰好是对的」 把两种漏法的特征各取了一半拼在了一起 —— 没有任何一种漏法同时具备这两个特征。

穷举所有子矩形实测（40 组 5~7 阶随机矩阵）：

漏在哪 出错率 方向 第一行 / 第一列
建表漏 - pre[i-1][j-1] 16930/18615 = 90.9% 全部偏大 ❌ 也会错（4141/5203）
查询漏 + pre[r1][c1] 9656/18615 = 51.9% 全部偏小 ✅ 恰好全对（0 个错）
  • 建表漏 → 左上角那块被加了两次没减掉 → 偏大，而且错误会顺着表往右下累积， 所以第一行也逃不掉。
  • 查询漏 → 左上角那块被减了两次没加回来 → 偏小；r1 = 0 或 c1 = 0 时 pre[r1][c1] 本来就是 0，加不加都一样，所以那两条边界真的恰好是对的。

⭐ 判据：看到结果偏小、且第一行第一列正常，去查查询公式； 偏大、且第一行也错，去查建表循环。 方向本身就是定位信息。

⚠️ 而「只用第一行做测试就发现不了」这句话只对查询漏成立。

🚨 数组会变就不能用

前缀和的全部前提是原数组不改。改一个元素，它后面所有的前缀和都要重算， 单次修改就是 O(n) —— 修改频繁时比不做预处理还慢。

「还慢」有多慢，实测（混合 upd 次单点修改 + qry 次区间查询）：

n 改:查 前缀和（每次改后重建） 暴力（改 O(1)、查 O(n)） 树状数组
20000 100:100 6.1 ms 2.1 ms 1.0 ms
20000 1000:1000 50.6 ms 2.5 ms 0.9 ms
50000 500:500 51.2 ms 3.1 ms 2.1 ms

⚠️ 第二行是关键：前缀和比什么都不做的暴力慢 20 倍，比树状数组慢 56 倍。 「不做预处理还慢」不是修辞。

场景 用什么
只查询，不修改 前缀和，O(n) 预处理 + O(1) 查询
查询 + 单点修改 树状数组 / 线段树，两者都是 O(log n)
查询 + 区间修改 线段树（带懒标记）

📌 树状数组和线段树在面试里出现频率不高，但**「前缀和不支持修改」这一句必须知道** —— 它是面试官追问「如果数组会变呢」时唯一想听的答案。

一个不那么显然的用法：前缀和 + 哈希表

「和为 k 的连续子数组有几个」—— 这题看着像滑动窗口， 但数组含负数时窗口不再单调，滑窗失效。

function subarraySum(nums, k) {
  const count = new Map([[0, 1]]);   // 🚨 前缀和为 0 的情况有 1 个（空前缀）
  let sum = 0, res = 0;

  for (const x of nums) {
    sum += x;
    res += count.get(sum - k) ?? 0;  // 有多少个前缀和等于 sum-k
    count.set(sum, (count.get(sum) ?? 0) + 1);
  }
  return res;
}

思路：以当前位置结尾、和为 k 的子数组个数 = 之前出现过多少次前缀和 sum - k。

🚨 new Map([[0, 1]]) 那个初始项不能省。它代表「什么都不取时前缀和为 0」， 少了它，从数组开头起算的那些子数组会被漏掉。

实测（3000 组随机数组，元素取 −3~3，与暴力对拍）：

正确版          3000 组全部与暴力一致
少了初始项      1203 组答案错（40.1%），累计漏掉 1778 个子数组
                ⚠️ 但仍有 1797 组（59.9%）答案照样正确

⚠️ 六成的用例发现不了它。 漏掉的只是「从下标 0 起算」的那些子数组， 只要答案里不含这一类，结果就完全正常。 📌 这和上面那个 i === 0 分支是同一种形状的 bug —— 都潜伏在「起点是 0」这个边界上。 造测试用例时专门构造一个答案必须包含前缀的例子，比多造十组随机用例管用。

⭐ 这个「前缀和 + 哈希表」的组合能处理负数， 是它相对滑动窗口的核心优势。

练习

勾选记录做过哪些，0 / 5 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。