区間和クエリが繰り返されるとき
地域図書館の運営担当者になったと想像してください。曜日別の訪問者数が [5, 8, 6, 3, 7, 9, 4] のように記録され、司書たちが一日に何十回も「2日目から5日目まで何人来ましたか?」と尋ねます。
質問のたびに最初から足すと、一クエリにO(N)、Q個のクエリでO(N×Q)となり遅すぎます。累積和(prefix sum) を使えば、前処理を一度するだけで全クエリをO(1)で応答できます。
累積和の核心アイデア
累積和配列 prefix を次のように定義します。
prefix[i] = visitors[0] + visitors[1] + ... + visitors[i-1]つまり prefix[i] は「最初からi個の要素の和」です。先頭に prefix[0] = 0(何も足さない和)を置くのが核心のトリックです。こうすると区間和の公式がきれいになります。
sum(l, r) = prefix[r + 1] - prefix[l]prefix[0] = 0 のおかげで、l = 0 の区間も例外なく同じ公式で処理されます。
実際に追ってみる
訪問者 [5, 8, 6, 3, 7, 9, 4] の累積和は次の通りです。
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| prefix | 0 | 5 | 13 | 19 | 22 | 29 | 38 | 42 |
区間 [2, 5] の和は直接足す必要がありません。
prefix[6] - prefix[2] = 38 - 13 = 25
検算: 6 + 3 + 7 + 9 = 25 ✓区間 [0, 2] も prefix[3] - prefix[0] = 19 - 0 = 19 と一発で出ます。
なぜ引き算で求まる?
prefix[r+1] は最初から r 番目までの和、prefix[l] は最初から l-1 番目までの和です。両者を引くと前の部分(0 ~ l-1)がちょうど相殺され、欲しい l ~ r の区間だけが残ります。図で見ると一目で理解できます。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 前処理 | O(N) |
| クエリ(1回) | O(1) |
| 全体(クエリQ個) | O(N + Q) |
| 空間 | O(N) |
クエリが多いほど累積和の威力が増します。クエリが一度だけなら前処理する価値はありませんが、同じ配列にクエリが繰り返されるなら累積和が圧倒的に有利です。
いつ使うとよい?
- •配列が固定されていて(要素が変わらない)、区間和クエリだけが繰り返し来るとき
- •「lからrまでの和」「部分和を繰り返し問う」タイプの問題
- •要素が頻繁に変わるなら、累積和ではなくセグメント木やフェニック木を検討してください。
AlgoNoteで直接確認しましょう
累積和配列がどう作られ、各区間クエリが引き算一回でどのように即座に答えになるか、AlgoNoteでステップごとに確認できます。