累積和
01 / 共通の仕組み
最初に一度 O(N) をかけて累積表を作っておけば、 その後の区間クエリはすべて定数時間の引き算に落ちる。逆向きに使えば、区間更新も安価にできる。
01 / 一文での本質
最初に一度 O(N) をかけて累積表を作っておく —— 以後の各区間クエリは 2 つの累積値の引き算 1 回で済む。
問題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
2 つの配列:下が入力 arr、上が累積表 prefix。累積は 1 マス長い。
ステップ
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] の和」
最も典型的なシグナル。配列は固定で、クエリは任意の順序・任意の回数で来る。1 回作って、何度でも問い合わせる。
「累計 / 累積」
配列に対して加法的な量 — 和、カウント、XOR — はすべて同じ手筋で扱える。
「クエリが多い」
クエリ数 ≥ 2 のときに初めて元が取れる。1 回しか問わないなら直接スキャンの方が速い。償却はクエリ回数に対して行われる。
「区間の平均値」
平均は和 ÷ 長さ — 同じ仕組み。
04 / よくある落とし穴
i.
+1 オフセットの境界 1 ずれ。累積配列は入力より 1 マス長い:
prefix[0] = 0、prefix[i+1] は arr[0..i] の和。閉区間クエリは prefix[r+1] − prefix[l]。このオフセットを無視すると、 先頭要素を取りこぼすかクエリ毎に過少計上する。ii.
累積を作った後で元配列を変更してしまう。
累積はスナップショット。
arr を変更すると、 変更位置以降の prefix はすべて失効する。配列が変わるならセグメント木やフェニック木 (BIT)を使う。iii.
長い配列での整数オーバーフロー。
累積和は単調増加する。固定幅整数の言語(Java、C++)では、入力の各要素が
int に収まっていても、累積表は long で持つ。05 / LeetCode で練習
難易度順に 4 問。あえて解答は載せていません。
— / どれをいつ使うか
1 次元線形
固定配列に対して区間和クエリが多く来る場合に使う。
区間和 · 累計 · LC 303
2 次元グリッド
行列上の矩形クエリ — 4 つの角で包除を取る。
矩形領域 · ブロック和 · LC 304
差分
逆向きに使う:区間更新を多く受け、最後に一度だけ各位置を読む。
区間加算 · カープール · フライト予約
ハッシュマップ
和がターゲットに等しい部分配列を数える — 累積和 + 既出前缀のマップ。
和 = K · K で割り切れる · LC 560