累積和で範囲合計

同じ範囲を、何度も足し直している

売上が日ごとに365件並んでいます。期間の合計を聞かれるたび、その範囲を足すなら、1回につき最大365回の足し算です。1000回とも全期間を聞かれれば、365 × 1000 = 365000 回になります。

足しているのは同じデータです。先に1回だけ累計を作れば、あとの質問には引き算で答えられます。365回の足し算と1000回の引き算なら、合計1365回です。ここでは足し算と引き算の回数だけを数えています。

電気メーターは、毎月ゼロに戻らない

電気メーターは使い始めからの累計を表示し続けます。今月の使用量は、今月の指針から先月の指針を引けば分かります。

# 検針0回目から4回目までの累計
meter = [0, 120, 265, 380, 510]
print(meter[3] - meter[1])   # 260

2か月目と3か月目の使用量は、265 - 120 = 145 と 380 - 265 = 115 です。足すと260です。累計同士を引いても 380 - 120 = 260 となり、途中の月を足し直す必要がありません。

先頭に0を1つ置いておく

累積和の配列をPと呼びます。Pの位置0には0を置き、位置kには先頭からk件の合計を置きます。元のデータがn件なら、Pはn + 1件です。

最初の0は、まだ1件も足していない状態です。これがあれば、最初の期間も他と同じ引き算で求められます。Pを作る時間は O(n)、追加のメモリも O(n) です。質問1回の計算は、期間の長さによらず O(1) になります。

データを更新した場合は、その後の累計も変わります。ここでは、元のデータが変わらず、同じ記録について何度も質問する場面を考えます。

どの端を含むかを決める

位置を0から数え、左端lを含み右端rを含まない区間なら、合計は P[r] - P[l] です。rまでの累計から、lより前の分を引きます。

一方、「2日目から4日目まで」のように両端を含み、日を1から数える場合は P[4] - P[1] です。位置と日付の数え方を混ぜないようにします。

解説

累積和は、何度も聞かれる計算を先に済ませる考え方です。データベースのインデックスや集計テーブルにも通じます。

例題で確かめる

5日間の売上が [6, 4, 9, 3, 8] 万円です。累計Pは [0, 6, 10, 19, 22, 30] になります。2日目から4日目まで、両端を含めた合計は P[4] - P[1] = 22 - 6 = 16 万円です。直接足しても 4 + 9 + 3 = 16 で一致します。最初の日の6万円だけを、4日目までの累計から引いています。