累積和
01 / 共通の仕組み
最初に一度 O(N) をかけて累積表を作っておけば、 その後の区間クエリはすべて定数時間の引き算に落ちる。逆向きに使えば、区間更新も安価にできる。
上から一つのサブパターンを選んでください。それぞれ単独でリンクできます — 問題に一番近いものから始めましょう。
↑ 選ぶ— / どれをいつ使うか
1 次元線形
固定配列に対して区間和クエリが多く来る場合に使う。
区間和 · 累計 · LC 303
2 次元グリッド
行列上の矩形クエリ — 4 つの角で包除を取る。
矩形領域 · ブロック和 · LC 304
差分
逆向きに使う:区間更新を多く受け、最後に一度だけ各位置を読む。
区間加算 · カープール · フライト予約
ハッシュマップ
和がターゲットに等しい部分配列を数える — 累積和 + 既出前缀のマップ。
和 = K · K で割り切れる · LC 560