累積和
01 / 共通の仕組み
最初に一度 O(N) をかけて累積表を作っておけば、 その後の区間クエリはすべて定数時間の引き算に落ちる。逆向きに使えば、区間更新も安価にできる。
01 / 一文での本質
各区間更新を l に +val と r+1 に −val の 2 点だけ記録し、最後に累積スキャンを 1 回 —— どれほど広い区間でも、更新 1 回は O(1)。
問題複数回の区間加算のあと、配列全体を読み出すn8更新(1,4,+3) (2,6,+2) (0,3,-1)
diff
·
0
·
1
·
2
·
3
·
4
·
5
·
6
·
7
·
8
final
·
0
·
1
·
2
·
3
·
4
·
5
·
6
·
7
上が長さ 9 の空の diff、下が長さ 8 の空の final。3 回の区間更新を適用してから累積スキャンする。
ステップ
0 / 17
フェーズ
更新
累計
·
0 / 17
02 / パターンの骨格
# 更新:arr[l..r] に val を O(1) で加えるdiff[l] ← diff[l] + valdiff[r+1] ← diff[r+1] − val# 仕上げ:累積スキャンで本配列を復元final[0] ← diff[0]for i in 1..n−1:final[i] ← final[i−1] + diff[i]# diff の長さは n+1。r+1 が常に合法なインデックスになる
03 / このパターンを使うべき合図
「arr[l..r] に val を加える」
最も典型的なシグナル。読み出しはすべての書き込みが終わったあとに来る、 交互には起きない。更新は何度でも、読み出しは 1 度だけ。
「予約 / 乗客 / イベント」
各予約は区間に対するカウント加算、各イベントはウィンドウのオン/オフ。 形は (start, end, delta) —— まさに差分配列の形。
「整数軸上の走査線」
端点をそのままインデックスにできるほど小さいなら、差分配列はソート不要の走査線。
「k 回更新後の最終配列」
更新数 ≥ 2 のときに初めて元が取れる。1 回しか更新しないなら直接書き換える方が速い。償却は更新回数に対して行われる。
04 / よくある落とし穴
i.
r+1 での −val を忘れる。2 点とも必須:
l での +val で増分をオンにし、r+1 での −val でオフにする。後者を忘れると、 増分が区間外へ漏れて、右側のすべてのマスが val だけ高くなる。ii.
右端の境界 1 ずれ。
閉じ位置は
r+1 であって r ではない。差分配列を n + 1 の長さで持てば、r+1 = n も合法な添え字になる。 累積スキャンの後でその末尾マスを捨てればよい。iii.
更新の途中で読んでしまう。
仕上げのスキャン前、
diff は本配列ではない —— 差分そのもの。 更新の途中で arr[i] を読むと結果は誤り。先に仕上げるか、 更新と問い合わせを交互に行うならフェニック木 (BIT) を使う。05 / LeetCode で練習
難易度順に 4 問。あえて解答は載せていません。
— / どれをいつ使うか
1 次元線形
固定配列に対して区間和クエリが多く来る場合に使う。
区間和 · 累計 · LC 303
2 次元グリッド
行列上の矩形クエリ — 4 つの角で包除を取る。
矩形領域 · ブロック和 · LC 304
差分
逆向きに使う:区間更新を多く受け、最後に一度だけ各位置を読む。
区間加算 · カープール · フライト予約
ハッシュマップ
和がターゲットに等しい部分配列を数える — 累積和 + 既出前缀のマップ。
和 = K · K で割り切れる · LC 560