前缀和
01 / 共享的机制
前置花一次 O(N) 构建累积表 —— 之后的每次区间查询就退化成一次常数级减法。 把这个套路反过来用,就能在区间更新上同样廉价。
01 / 一句话本质
前置花一次 O(N) 建好累计表 —— 之后的每次区间查询就是两个前缀的一次减法。
题目O(1) 求 arr[l..r] 的和输入[3, 1, 2, 5, 4, 2, 1, 3]查询arr[2..5]
prefix
·
0
·
1
·
2
·
3
·
4
·
5
·
6
·
7
·
8
arr
3
0
1
1
2
2
5
3
4
4
2
5
1
6
3
7
两条数组:下面是输入 arr,上面是前缀表 prefix。前缀比输入多一格。
步
0 / 14
阶段
构建
结果
·
0 / 14
02 / 模式骨架
# 一次性建好前缀表prefix[0] ← 0for i in 0..n−1:prefix[i+1] ← prefix[i] + arr[i]# 查询:arr[l..r] 的和,O(1)rangeSum(l, r) ← prefix[r+1] − prefix[l]# prefix[i] = arr[0..i−1] 的和 —— “+1 偏移”让 l = 0 也能统一处理
03 / 什么时候用这个模式
"arr[l..r] 的和"
最典型的信号。数组不变,查询可以任意顺序、任意次数。建一次,查无数次。
"累计 / 累加"
任何对数组可加性的量 —— 和、计数、异或 —— 都适用同一套路。
"多次查询"
只有查询次数 ≥ 2 时才划算。单次查询不会比直接扫快。摊销是相对于查询次数而言的。
"窗口内的平均值"
平均值就是和除以长度 —— 同一套机器。
04 / 常见坑
i.
+1 偏移的差一错误。前缀数组比输入多一格:
prefix[0] = 0,且 prefix[i+1] 是 arr[0..i] 的和。闭区间查询为 prefix[r+1] − prefix[l]。 忽略这个偏移要么漏掉首元素,要么每次查询少算。ii.
建完前缀后改动原数组。
前缀是一份快照。
arr 一旦改动,改动位置之后的每一格 prefix 都失效。如果数组会动,改用线段树或树状数组。iii.
长数组上的整数溢出。
前缀和是单调增长的;固定宽度整数的语言(Java、C++)里,即便输入元素能放进
int, 前缀表也要用 long。05 / 去 LeetCode 上练习
四道题,按难度排序。这里有意不放解答。
— / 什么时候用哪个
一维线性
当对一个固定数组有很多次区间求和查询时使用。
区间和 · 累计 · LC 303
二维网格
用于矩阵上的矩形查询 —— 四个角上做容斥。
矩形区域 · 块和 · LC 304
差分
反过来用:很多次区间更新,最后一次性扫出每个位置的值。
区间加 · 拼车 · 航班预订
哈希映射
统计和等于目标值的子数组数 —— 前缀和 + 已见前缀的哈希表。
和为 K · 整除 K · LC 560