累積和
01 / 共通の仕組み
最初に一度 O(N) をかけて累積表を作っておけば、 その後の区間クエリはすべて定数時間の引き算に落ちる。逆向きに使えば、区間更新も安価にできる。
01 / 一文での本質
実行中の累積和を 1 度だけ流す —— 各時点でここを末尾とする 有効な部分配列の数は、ハッシュマップがすでに記録している prefix − k の出現回数に等しい。
問題和 = k の部分配列をカウント入力[1, 2, 3, -1, 2, 3]k5
prefix0
arr
1
0
2
1
3
2
-1
3
2
4
3
5
map
0·1
arr を左から右へ走査する。目標は k = 5。ハッシュマップは { 0: 1 } をシードしておく —— このエントリだけで添字 0 から始まる部分配列を扱える。
ステップ
0 / 19
フェーズ
初期化
prefix
0
検索値
·
ヒット
·
カウント
0
0 / 19
02 / パターンの骨格
# arr を走査しつつハッシュを保つcount ← 0prefix ← 0map ← { 0: 1 } # 空の累積のシードfor x in arr:prefix ← prefix + x# 検索if (prefix − k) in map:count += map[prefix − k]map[prefix] += 1 # 今の累積を登録し、以後の検索に備える
03 / このパターンを使うべき合図
「和が k の部分配列の個数」
最も典型的なシグナル。部分配列の和は 2 つの累積の差なので、
i を末尾とする有効な部分配列はすべて、過去のある累積値 prefix[i] − k に対応する。ループの入れ子ではなく検索。「k で割り切れる部分配列」
同じ発想。ハッシュのキーを
prefix ではなく prefix mod k にするだけ。k に関して加法的な量ならすべて適用できる。「+1 / −1 の累積」
値を変換して(例えば
0 → −1)、求めたい性質を「累積が等しい」に置き換える。 以後は同じハッシュの手筋で一致を数える。「性質 P を満たす最長 / 最短部分配列」
仕組みは同じだが、各累積値については最初に出現した位置を記録し、答えは
i − map[prefix − k]。カウントから添字検索に変わる。04 / よくある落とし穴
i.
{ 0: 1 } シードを忘れる。このシードは添字 0 から始まる部分配列を扱うためのもの —— つまり
prefix[i] 自体が k に等しい場合だ。 これがないと、それ自体で目標と等しい累積がすべて静かに漏れる。ii.
検索より前に累積を登録してしまう。
順序は先に検索、後に登録。先に
map[prefix] += 1 をすると、k = 0 のとき長さ 0・和 0 の「部分配列」が自分自身を数えてしまう。 検索時のハッシュには厳密により早い位置の累積しか入っていてはならない。iii.
頻度ではなく 1 を加算してしまう。
正しくは
count += map[prefix − k]、count += 1 ではない。 同じ累積値は何度も出現し得るし(特に負数や 0 を含む場合)、その一つひとつが i を末尾とする別個の部分配列に対応する。05 / LeetCode で練習
難易度順に 4 問。あえて解答は載せていません。
— / どれをいつ使うか
1 次元線形
固定配列に対して区間和クエリが多く来る場合に使う。
区間和 · 累計 · LC 303
2 次元グリッド
行列上の矩形クエリ — 4 つの角で包除を取る。
矩形領域 · ブロック和 · LC 304
差分
逆向きに使う:区間更新を多く受け、最後に一度だけ各位置を読む。
区間加算 · カープール · フライト予約
ハッシュマップ
和がターゲットに等しい部分配列を数える — 累積和 + 既出前缀のマップ。
和 = K · K で割り切れる · LC 560