前缀和

01 / 共享的机制

前置花一次 O(N) 构建累积表 —— 之后的每次区间查询就退化成一次常数级减法。 把这个套路反过来用,就能在区间更新上同样廉价。

01 / 一句话本质
前置花一次 O(N · M) 建好角表 —— 之后的每次矩形求和就是在四个前缀角上做一次容斥。
题目O(1) 求 mat[r1..r2][c1..c2] 的和矩阵5×5矩形(1,1)..(3,3)
mat
3
0
1
4
2
5
6
3
2
1
1
2
0
1
5
4
1
0
1
7
1
0
3
0
5
prefix
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
两块网格:左边是输入 mat,右边是前缀表 prefix。前缀表在顶行和左列各多出一行/一列的 0。
步
0 / 31
阶段
构建
结果
·
0 / 31

02 / 模式骨架

# 一次性建好二维前缀表prefix[0][*] ← 0; prefix[*][0] ← 0for i in 0..n−1:for j in 0..m−1:prefix[i+1][j+1] ← mat[i][j]+ prefix[i][j+1] + prefix[i+1][j] − prefix[i][j]# 查询:用容斥求矩形 (r1, c1)..(r2, c2) 的和rectSum(r1, c1, r2, c2) ←prefix[r2+1][c2+1] − prefix[r1][c2+1] − prefix[r2+1][c1] + prefix[r1][c1]# 减去多算的两条带,再把重复扣掉的那个角加回来

03 / 什么时候用这个模式

"矩阵中某个矩形的和"
最典型的信号。矩阵不变,查询可以任意顺序、任意次数。建一次,查无数次 —— 只是放到二维。
"块和 / 子矩阵和"
块、瓦片、窗口、区域 —— 凡是读取一块连续矩形单元的,都能塌缩成四次角点读取。
"四角容斥"
这个套路的视觉抓手。两个大矩形在一个角上重叠 —— 两次都减掉,然后加回来一次。
"很多次矩形查询"
摊销规律和一维相同 —— 查询次数太少不划算。单次矩形求和不会比朴素扫描快。

04 / 常见坑

i.
忘了把那个角加回来。
两次减法(prefix[r1][c2+1] 与 prefix[r2+1][c1])都包含了左上角的矩形 (0,0)..(r1−1, c1−1) —— 你把它减了两次。+ prefix[r1][c1]再把它补回来一次。漏掉这步,每次查询都正好少算这个角的和。
ii.
在两个维度上同时出现 +1 偏移的差一错误。
前缀表大小是 (n+1) × (m+1),首行首列填 0。读表时,包含边界的远角是 r+1 / c+1,不包含边界的近角是 r / c。在同一次查询里把两种约定混用,是这里最常见的 bug 来源。
iii.
构建时递推方向不对。
每个 prefix[i+1][j+1] 都要读三个已经算好的格子(上、左、左上)。 必须行外层、列内层(或相反)地扫,绝不能斜着走或从下往上 —— 否则读到的是旧值。

05 / 去 LeetCode 上练习

四道题,按难度排序。这里有意不放解答。

01Range Sum Query 2D — Immutable— LC 304中等→02Matrix Block Sum— LC 1314中等→03Find Kth Largest XOR Coordinate Value— LC 1738中等→04Max Sum of Rectangle No Larger Than K— LC 363困难→

— / 什么时候用哪个

一维线性
当对一个固定数组有很多次区间求和查询时使用。
区间和 · 累计 · LC 303
二维网格
用于矩阵上的矩形查询 —— 四个角上做容斥。
矩形区域 · 块和 · LC 304
差分
反过来用:很多次区间更新,最后一次性扫出每个位置的值。
区间加 · 拼车 · 航班预订
哈希映射
统计和等于目标值的子数组数 —— 前缀和 + 已见前缀的哈希表。
和为 K · 整除 K · LC 560