累積和で範囲合計
同じ範囲を、何度も足し直している
売上が日ごとに 365 件並んでいるとします。「4 月分の合計は」「5 月から 7 月は」「今年の前半は」と聞かれるたびに、その範囲を頭から足していくと、1 回の質問につき最大 365 回の足し算です。質問が 1000 回来れば、36 万回になります。
けれど、足しているのはいつも同じ数字たちです。何度も足し直すのではなく、先に 1 回だけ足しておいて、あとは引き算で取り出す ことができます。
Python
print(365 * 1000) # 毎回足し直すと 36 万 5000 回
print(365 + 1000) # 先に累計を作れば 1365 回下ごしらえが 365 回、質問は 1 回あたり数回。質問が増えるほど差が開きます。
電気メーターは、毎月ゼロに戻らない
この仕組みは、電気のメーターとまったく同じです。メーターは使い始めからの累計を表示し続け、毎月ゼロには戻りません。だから今月の使用量は、今月の指針から先月の指針を引くだけで出ます。
Python
# 検針 0 回目から 4 回目までの、累計の指針
meter = [0, 120, 265, 380, 510]
# 2 回目と 3 回目の 2 か月ぶん
print(meter[3] - meter[1]) # 260265 - 120 = 145 と 380 - 265 = 115 を足しても 260 です。途中の月をいちいち足さなくても、両端の 2 つを引けば答えが出ます。累計を持っておくというのは、こういうことです。
先頭に 0 を 1 つ置いておく
メーターの一覧の先頭に 0 が入っているのは、飾りではありません。「まだ 1 回も使っていない状態」を表す、れっきとした 1 件です。
これが無いと、いちばん最初の期間だけ引く相手がいなくなり、そこだけ特別扱いのコードを書く羽目になります。先頭に 0 を置いておけば、最初の期間も他とまったく同じ形の引き算で求められます。だから累計の一覧は、元のデータより 1 つ長く なります。ここを同じ長さで作ってしまうと、最後の期間を取り出すときに範囲の外へ手が伸びます。
どこからどこまでか、を先に決める
累積和でいちばん間違えるのは、足し算ではなく 端の扱い です。
Python
days = [10, 20, 30, 40, 50]
print(days[1:3]) # [20, 30] 3 番目は入らない
print(days[1:4]) # [20, 30, 40]「3 番目から 5 番目まで」と言ったとき、5 番目を含むのか含まないのかで、引く相手が 1 つずれます。含む約束と含まない約束では、正しい式が別物になります。どちらで書かれた仕様なのかを先に読み、小さなデータで手計算して答え合わせをしてから、本番のデータに通してください。
累積和は「あとで何度も聞かれるなら、先に払っておく」という考え方の入口です。データベースのインデックスや集計テーブルも、根っこは同じ発想です。
要件
- 累積和 prefix を一度作り、prefix[r+1] - prefix[l] で範囲合計を求めること
- 0 <= l <= r < len(arr) を前提として良い
- 戻り値は整数 (int)
入出力例
rangeSum([1,2,3,4,5], 1, 3) → 9
rangeSum([1,2,3,4,5], 2, 2) → 3
rangeSum([1,2,3,4,5], 0, 4) → 15
rangeSum([10,20,30,40], 0, 2) → 60
rangeSum([10,20,30,40], 2, 3) → 70
rangeSum([-1,2,-3,4,-5], 1, 3) → 3ヒント
