数组基础与常用操作

差分数组技巧

它是前缀和的镜像

前缀和解决「反复查询区间和」。差分数组解决反过来的那件事：反复修改一整个区间，最后才看结果。

前缀和：预处理一次 → 每次查询 O(1)
差分数组：每次修改 O(1) → 最后还原一次

⭐ 两者是互逆运算：对差分数组求前缀和，就得回原数组。这不是巧合，是定义决定的。

定义

// diff[i] = nums[i] - nums[i-1]，diff[0] = nums[0]
function buildDiff(nums) {
  const diff = new Array(nums.length);
  diff[0] = nums[0];
  for (let i = 1; i < nums.length; i++) diff[i] = nums[i] - nums[i - 1];
  return diff;
}

// 还原：对 diff 求前缀和
function restore(diff) {
  const res = new Array(diff.length);
  res[0] = diff[0];
  for (let i = 1; i < diff.length; i++) res[i] = res[i - 1] + diff[i];
  return res;
}

nums = [8,5,9,6,1] → diff = [8,-3,4,-3,-5] → 还原回 [8,5,9,6,1]。

⭐ 区间加减为什么只动两个位置

要给闭区间 [i, j] 里每个元素都加 val：

function increment(diff, i, j, val) {
  diff[i] += val;
  if (j + 1 < diff.length) diff[j + 1] -= val;
}

就两行。 想清楚为什么，这个技巧就算掌握了：

diff[i] += val 意味着「从下标 i 开始，后面每一个还原值都多了 val」—— 因为还原是累加，i 处的增量会一路传到末尾。

但我们只想影响到 j 为止，所以在 j+1 处减回来，把这个增量掐断。

原数组      [8, 5, 9, 6, 1]
给 [1,3] 加 3
diff        [8, -3, 4, -3, -5]
diff[1]+=3  [8,  0, 4, -3, -5]
diff[4]-=3  [8,  0, 4, -3, -8]
还原        [8,  8, 12, 9, 1]
                ↑------↑ 这三个各加了 3，两头没动

🚨 if (j + 1 < diff.length) 不能省。区间一直延伸到数组末尾时， j+1 越界；JavaScript 里 diff[5] -= 3 不报错，它会给数组挂一个下标为 5 的元素，length 悄悄变成 6。实测：

const diff = [8, -3, 4, -3, -5];   // length 5
diff[5] -= 3;
// → length 变成 6，且 diff[5] === NaN（undefined - 3）

还原结果   [8, 5, 9, 6, 1, NaN]
           └──── 前 5 个全对 ────┘  └ 多出来的这一位是 NaN

⚠️ 症状有两层，第一层比第二层更难查：

长度多了一位 —— 前面所有元素都是对的，很容易被当成别处的问题
多出来的那一位是 NaN，不是 -3 —— 因为 undefined - 3 = NaN

⭐ 「前面所有元素都是对的」不是随口一说。把 if 去掉，跑 20000 组随机数据（长度 1~~15、每组 1~~6 次区间加减）与朴素做法对拍：

长度比正确答案长了一位     14603 组
【前 n 个元素】出错          0 组      ← 前面真的一个不差

⭐ 第 2 点其实是好事：NaN 比一个看着正常的数字显眼得多。真正危险的是你只检查前几个元素，那样两层症状都看不见。 📌 判据：这类 bug 要拿「长度」当第一道检查，别只比内容。

复杂度对比

k 次区间修改、最后读一次结果：

	朴素做法	差分数组
每次修改	O(区间长度)	O(1)
最后还原	0	O(n)
总计	O(Σ区间长度)	O(k + n)

🚨 朴素那一栏常被写成 O(k·n)，那其实假设了「每次都改整个数组」。 区间是随机子区间时平均长度约 n/3，成本只有 k·n/3。这个区别直接决定交叉点在哪，所以下面每张表都会写明区间口径。

⭐ 先看与机器、与实现都无关的操作数（n = 100000）：

k       Σ区间长度（随机子区间）   Σ区间长度（整区间）   差分 2k+n
1              17,883               100,000          100,002
10            303,181             1,000,000          100,020
100         2,515,377            10,000,000          100,200
1000       25,294,919           100,000,000          102,000

⭐ k=1000 那行就是「数量级差距」的来源：整区间口径下朴素 1 亿次、差分 10.2 万次。

⚠️ 但操作数打平的地方，不是耗时打平的地方

按操作数算，交叉点该在 k·n = 2k+n → k ≈ 1（整区间）。实测差着五倍：

整区间 [0, n-1]                        随机子区间
k     朴素      差分     谁快          k     朴素      差分     谁快
1     0.05     0.30    朴素 5.80×     1     0.04     0.25    朴素 6.85×
4     0.20     0.29    朴素 1.44×    10     0.12     0.28    朴素 2.30×
5     0.27     0.27    持平          20     0.24     0.28    朴素 1.17×
6     0.30     0.28    差分 1.07×    25     0.28     0.28    持平
10    0.51     0.30    差分 1.68×    30     0.37     0.28    差分 1.31×
30    1.53     0.29    差分 5.29×    40     0.52     0.29    差分 1.79×

🚨 交叉点整区间是个位数，随机子区间是几十 —— 相差三到五倍，全看区间怎么取。

⚠️ 具体到哪个 k，这台机器上量不准。把整个扫描重复 5 轮（每轮换随机种子）：

轮次   整区间   随机子区间
 1     6~7      15~20
 2     5~6      25~30
 3     5~6      20~25
 4     5~6      20~25
 5     5~6      15~20

⭐ 整区间那一列还算稳（5 轮里 4 轮都是 5~~6）；随机子区间那一列自己就在 15~~30 之间摆 —— 因为 Σ区间长度本身随种子变。

🚨 更糟的是机器负载会把整张表一起抬起来。同一段代码、预热之后、连测 5 批各 21 次取中位数，在负载 8.7 的机器上：

5 批的中位数   0.648 / 0.764 / 0.714 / 0.580 / 0.586 ms
批间极差       0.184 ms（相对 32%）

⚠️ 连「中位数」本身都在批与批之间漂 32% —— 而交叉点附近两边的差异只有 0.02~0.05 ms。在这种负载下，交叉点具体落在 5 还是 8，量出来的是负载不是算法。

🚨 而这个漂移量自己也不稳定：换个时间再测，同样的 5 批只漂 5%。所以连「噪声有多大」都不能只量一次。相比之下单次测量的抖动一直稳定在 3.5~5 倍 （p10~p90 0.49~~1.27，极值 0.48~~1.82）—— 那才是可以写下来的量。

👉 所以这一节要记的不是数字，是三条关系：

k 小的时候朴素更快（差分白付两趟 O(n)）
k 大的时候差分快出数量级（k=1000 时 30 倍以上）
交叉点随「区间平均有多长」右移 —— 区间越短，朴素越便宜，差分越晚才划算

📌 判据：报交叉点之前先量噪声下限。 噪声比要测的差异还大时，就只报关系、不报数字。

📌 为什么操作数算不准：预热后单独量两边的单位成本 ——

朴素扫一遍全数组（含一次 slice）      0.114 ms
差分的固定开销（build + restore）     0.307 ms   ← 两趟 O(n) 外加两次数组分配
                                                  ≈ 朴素的 2.7 倍

⭐ 差分那两趟的单位成本比朴素那一趟贵近三倍，所以真实交叉点比「操作数打平」预测的位置往右挪。操作数只能给量级，交叉点必须实测。

⭐ 差分那一列确实几乎是平的（中位数全在 0.25~0.30 ms），因为它的成本主要是 build + restore 那两趟 O(n)，与修改次数几乎无关。这和前缀和那张表是镜像的。

🚨 这组数据里噪声比信号大，两个坑都踩过：

不预热的首次测量    朴素单遍 1.311 ms / 差分固定开销 1.729 ms
预热 50 次之后      朴素单遍 0.114 ms / 差分固定开销 0.307 ms   ← 差 11 倍
同一组参数连测 61 次（差分）  中位数 0.28   p10~p90 0.26~0.51   最小~最大 0.25~1.21

⚠️ 单次测量的抖动能到 4.8 倍，比这里要测的差异还大。 👉 所以：先预热，再取中位数，最后把区间口径写出来 —— 三样缺一样，量到的就是噪声。

典型题：航班预订

题意复述：有 n 个航班（编号 1~n），给一批预订记录 [first, last, seats] 表示从 first 到 last 每个航班都预订了 seats 个座位。求每个航班总共被预订了多少座位。

一眼就是差分：区间整体加，最后统一读。

function corpFlightBookings(bookings, n) {
  const diff = new Array(n).fill(0);

  for (const [first, last, seats] of bookings) {
    diff[first - 1] += seats;                  // 🚨 题目是 1-indexed
    if (last < n) diff[last] -= seats;         // last 已经是 0-indexed 的 last+1
  }

  const res = new Array(n);
  res[0] = diff[0];
  for (let i = 1; i < n; i++) res[i] = res[i - 1] + diff[i];
  return res;
}

⚠️ 这题最容易错的不是差分本身，是下标基准。题目给的是 1-indexed，数组是 0-indexed，于是 first-1 是起点、而 last（不减 1）恰好就是「终点后一位」。两个减 1 只减了一个 —— 看起来不对称，但确实是对的。

「看起来对称」地把两个都减 1，实测 2000 组随机数据全错，100% （并穷举了 n=1~~4、单条预订、权 1~~3 的全部 60 种情形，没有一种能让错版侥幸对上）：

n=6，预订 [[6,6,5],[3,6,9]]
正确        [0, 0, 9, 9, 9, 14]
两个都减 1  [0, 0, 9, 9, 9,  0]
                            ↑ 最后一个航班的座位全丢了

⭐ 症状很干净：每个区间的最后一个位置被漏掉（增量提前一位被掐断）。单区间的 3000 个用例里，3000 个的差异都恰好是「下标 last-1 那一位少了 seats」 —— 一个别的位置都没动。看到「结果的尾巴不对」就该查这里。 📌 100% 出错也意味着随便造一个用例就能发现它 —— 和上面那些「触发条件很窄」的 bug 正好相反，这类反而是最不危险的。 ⚠️ 对照一下这一篇里的两个 bug：漏掉 if (j+1 < len) 那个答案全对、只是长度多一位， corpFlightBookings 里减错下标那个每次都错、错得很显眼。 越安静的越危险，和出错率高低无关。

📌 遇到 1-indexed 的题，先把「起点」和「终点后一位」这两个量单独写出来再动手，比在脑子里同时转换两个基准可靠得多。

判据

看到这三个特征同时出现，就是差分：

对连续区间整体加减
修改很多次
中途不需要读，最后统一出结果

📌 少任何一条都不划算。中途要读的话，每次读之前都得还原一遍，优势立刻没了 —— 那种情况要上线段树。

练习

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

1109. 航班预订统计中等差分数组的裸题，注意 1-indexed
1094. 拼车中等区间加 + 检查是否超上限
598. 区间加法 II简单变形，想清楚什么才是「区间」
56. 合并区间中等不是差分，但同属区间处理，拿来对照

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