累積和
01 / 共通の仕組み
最初に一度 O(N) をかけて累積表を作っておけば、 その後の区間クエリはすべて定数時間の引き算に落ちる。逆向きに使えば、区間更新も安価にできる。
01 / 一文での本質
最初に一度 O(N · M) をかけて角の表を作っておく —— 以後の各矩形和クエリは 4 つの角での包除一発で済む。
問題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
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
2 つのグリッド:左が入力 mat、右が累積表 prefix。累積表は上端と左端に 0 で埋めた 1 行・1 列が余分に付く。
ステップ
0 / 31
フェーズ
構築
結果
·
0 / 31
02 / パターンの骨格
# 2 次元累積表を一度だけ作る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]# はみ出した 2 つの帯を引き、二重に引いた角を 1 回足し戻す
03 / このパターンを使うべき合図
「行列中の矩形の和」
最も典型的なシグナル。行列は固定で、クエリは任意の順序・任意の回数で来る。1 回作って、何度でも問い合わせる —— ただし 2 次元で。
「ブロック和 / 部分行列の和」
ブロック、タイル、ウィンドウ、領域 —— 連続した矩形セルを読むものはすべて、4 回の角読みに潰せる。
「4 角での包除」
このパターンの視覚的なフック。2 つの大きな矩形が 1 つの角で重なる —— 両方とも引いて、1 回だけ足し戻す。
「矩形クエリが多い」
償却の話は 1 次元と同じ —— クエリ数が少ないと割に合わない。1 回限りなら素朴スキャンの方が速い。
04 / よくある落とし穴
i.
角を足し戻すのを忘れる。
2 つの引き算(
prefix[r1][c2+1] と prefix[r2+1][c1])はどちらも左上の矩形 (0,0)..(r1−1, c1−1) を含んでいる —— つまり 2 回引いてしまっている。+ prefix[r1][c1] でちょうど 1 回戻す。これを落とすと、毎回その角の分だけ答えが小さくなる。ii.
両次元での
+1 オフセットの境界 1 ずれ。累積表は
(n+1) × (m+1)、先頭行と先頭列はゼロ埋め。含む側の遠い角は r+1 / c+1、含まない側の近い角は r / c。 1 つのクエリの中で 2 つの規約を混ぜるのが、ここで最も多いバグの原因。iii.
構築の漸化式を間違った方向で回す。
各
prefix[i+1][j+1] は既に計算済みの 3 マス(上、左、左上)を読む。 行を外、列を内(あるいは逆)で回さなくてはいけない —— 斜めや下から上ではダメで、 古い値を読んでしまう。05 / LeetCode で練習
難易度順に 4 問。あえて解答は載せていません。
— / どれをいつ使うか
1 次元線形
固定配列に対して区間和クエリが多く来る場合に使う。
区間和 · 累計 · LC 303
2 次元グリッド
行列上の矩形クエリ — 4 つの角で包除を取る。
矩形領域 · ブロック和 · LC 304
差分
逆向きに使う:区間更新を多く受け、最後に一度だけ各位置を読む。
区間加算 · カープール · フライト予約
ハッシュマップ
和がターゲットに等しい部分配列を数える — 累積和 + 既出前缀のマップ。
和 = K · K で割り切れる · LC 560