差分数组:区间批量加,为什么只改两个位置就够了

之前高峰在线人数那几篇里"线性扫描"背后真正用的数据结构就是它。核心思路:要给数组一段区间统一加上一个数,直接遍历这段区间要 O(区间长度);但如果维护的是"相邻两项的差值"而不是数值本身,这个操作只需要改两个位置,最后统一做一次前缀和就能把所有区间加总的结果一次性还原出来。

真实验证:差分数组 vs 暴力遍历,结果完全一致

连续做 4 次区间加操作:[1,5)+2、[3,9)+1、[6,8)+3、[0,4)-1,分别用暴力法(每次直接遍历区间内每个位置)和差分数组法(每次只改两个端点,最后统一前缀和)跑一遍:

真实实测

ops = [(1,5,2), (3,9,1), (6,8,3), (0,4,-1)]
brute  = brute_force_range_add(12, ops)   # 暴力法
diffed = diff_array_range_add(12, ops)    # 差分数组法

暴力法结果 : [-1, 1, 1, 2, 3, 1, 4, 4, 1, 0, 0, 0] 差分数组结果: [-1, 1, 1, 2, 3, 1, 4, 4, 1, 0, 0, 0] 完全一致 : True

真实验证:50 万长度数组,2 万次区间加,真实测出快多少

数组长度 50 万,做 2 万次随机区间加(每次区间长度随机、最长 5000),暴力法和差分数组法各跑一遍,真实计时:

真实实测

n = 500_000
ops = [(随机区间, 随机+/-5)  for _ in range(20_000)]

两者结果完全一致: True 暴力法耗时 : 983.8 ms 差分数组耗时: 13.5 ms 提速倍数 : 72.9x

区间越长、次数越多,暴力法要遍历的总位置数就越多;差分数组不管区间多长,每次操作永远只碰两个位置,复杂度只跟"操作次数"有关,跟"区间长度"完全无关——这就是 72.9 倍差距的根本原因。

真实验证:接上高峰在线人数的例子,结果一致

"用户在线区间 [login, logout) 内人数 +1"本质就是一次区间加操作。拿高峰在线人数那篇验证过的例子直接对上号:

真实实测

records = [("A",1,4), ("B",2,6), ("C",5,7)]  # 三次区间 +1 操作
diff_array_range_add(8, [(1,4,1), (2,6,1), (5,7,1)])

还原出的每秒在线人数: [0, 1, 2, 2, 1, 2, 1, 0] 峰值 = 2 (在 t=2,3 和 t=5)

跟之前扫描线和持续时长两篇里验证过的结果完全一致——"登录 +1、登出 -1、逐秒累加"这套写法,本质就是差分数组处理"区间批量 +1"这个特例。合并区间这道经典题也能用差分数组解——只是这次关心的不是"累加次数",而是"覆盖次数 > 0 的连续段"。

一句话总结: 差分数组 diff 记录的是"相邻两项差多少",不是数值本身。给区间 [l, r) 整体加 k,只需要 diff[l] += k(从这里开始多了 k)和 diff[r] -= k(到这里为止,之前多加的 k 要抵消掉),两步 O(1)。不管做了多少次这样的操作,最后对 diff 跑一遍前缀和(cur += diff[i]),就能一次性还原出所有区间加总后的真实数值,整个还原过程只需要遍历一次,O(n)。

0 / 0

4 次区间加,先改差分数组,再统一前缀和还原

差分数组 diff[](操作只改两个端点)

还原后的数组 A[](前缀和逐格展开)

diff[l] += k(区间起点) diff[r] -= k(区间终点,抵消) 已还原出的 A[i]

当前步骤

—

4 次区间加操作:[1,5)+2 [3,9)+1 [6,8)+3 [0,4)-1。点击"下一步"看差分数组怎么记录这些操作,以及最后怎么用前缀和一次性还原出真实数组。