前缀和
01 / 共享的机制
前置花一次 O(N) 构建累积表 —— 之后的每次区间查询就退化成一次常数级减法。 把这个套路反过来用,就能在区间更新上同样廉价。
01 / 一句话本质
把每次区间更新记成 l 处 +val 与 r+1 处 −val 两笔,最后做一次前缀扫描 —— 无论区间多宽,每次更新都是 O(1)。
题目多次区间加之后,一次性读出整个数组n8更新(1,4,+3) (2,6,+2) (0,3,-1)
diff
·
0
·
1
·
2
·
3
·
4
·
5
·
6
·
7
·
8
final
·
0
·
1
·
2
·
3
·
4
·
5
·
6
·
7
上面是长度 9 的空 diff,下面是长度 8 的空 final。准备应用 3 次区间更新,然后做一次前缀扫描。
步
0 / 17
阶段
更新
累计
·
0 / 17
02 / 模式骨架
# 更新:O(1) 给 arr[l..r] 加上 valdiff[l] ← diff[l] + valdiff[r+1] ← diff[r+1] − val# 收尾:前缀扫描还原完整数组final[0] ← diff[0]for i in 1..n−1:final[i] ← final[i−1] + diff[i]# diff 长度为 n+1,所以 r+1 永远是合法下标
03 / 什么时候用这个模式
"给 arr[l..r] 加 val"
最典型的信号。所有读取都发生在所有写入之后,二者不交错。多次更新,一次读取。
"预订 / 乘客 / 事件"
每条预订在某个区间上加计数,每个事件开关一个窗口。形状就是(start, end, delta) —— 这正是差分数组的形状。
"整数轴上的扫描线"
当端点小到可以直接当下标时,差分数组就是省掉排序的扫描线。
"k 次更新后的最终数组"
只有更新次数 ≥ 2 时才划算。单次更新不会比直接覆盖整段更快。摊销是相对于更新次数而言的。
04 / 常见坑
i.
漏掉
r+1 处的 −val。两笔都要写:
l 处 +val 把增量打开,r+1 处 −val 把它关掉。漏掉后一笔,增量就会泄到区间之外 —— 右侧的每一格都会多 val。ii.
右端点的差一错误。
关闭点在
r+1,不是 r。把差分数组开成 n + 1 的长度,这样 r+1 = n 也是合法下标;前缀扫描后再丢掉末尾那格即可。iii.
更新过程中就去读。
收尾扫描之前,
diff 不是原数组,而是差分。在更新中途读任何 arr[i] 都会得到错误结果;要么先收尾,要么改用树状数组处理交错的更新与查询。05 / 去 LeetCode 上练习
四道题,按难度排序。这里有意不放解答。
— / 什么时候用哪个
一维线性
当对一个固定数组有很多次区间求和查询时使用。
区间和 · 累计 · LC 303
二维网格
用于矩阵上的矩形查询 —— 四个角上做容斥。
矩形区域 · 块和 · LC 304
差分
反过来用:很多次区间更新,最后一次性扫出每个位置的值。
区间加 · 拼车 · 航班预订
哈希映射
统计和等于目标值的子数组数 —— 前缀和 + 已见前缀的哈希表。
和为 K · 整除 K · LC 560