累積和

累積和は、繰り返される区間和のクエリを定数時間の処理に変えます。配列を 1 回走査して累計 prefix[k] = nums[0] + … + nums[k − 1] を書いておけば、任意の連続区間 nums[l..r] の和は prefix[r + 1] − prefix[l] です。読むのは 2 つ、引き算は 1 回。区間が 1 マスでも配列全体でも変わりません。

ドライブのオドメーターを思い浮かべてください。町に着くたびに表示を書き留めておけば、ある区間の長さを知るためにもう一度走る必要はありません。町 2 から町 6 までの距離は、2 つの読みの差です。累積和は配列に同じことをします。仕事を質問のときから、先に済ませる 1 回の記帳へ移すのです。

累積和の仕組み

隣り合うマスの間ごとに区切りを立て、最初のマスの前と最後のマスの後にも 1 本ずつ立てます。長さ n の配列には n + 1 本の区切りがあり、番号は 0 から n です。すると prefix[k] は区切り k より左にあるすべての値の合計です。区切り 0 の左には何もないので prefix[0] = 0、prefix[n] は配列全体の和になります。

構築はループ 1 つです。各項目は前の項目に、いま通り過ぎたマスを足したもの：prefix[k] = prefix[k − 1] + nums[k − 1]。足し算は n 回、一度だけです。

nums[l..r]（両端を含む）のクエリには、区間を挟む 2 本の区切りを使います。区切り l は nums[l] の直前、区切り r + 1 は nums[r] の直後にあります。区切り r + 1 より左の全部から区切り l より左の全部を引けば、ちょうどその区間が残ります。共通部分 nums[0..l − 1] は打ち消し合います。クエリは 1 行でループはなく、コストは r − l に依存しません。

先頭の 0 には役目があります。prefix[0] = 0 がなければ、l = 0 から始まるクエリには引く値がなく、専用の分岐が必要になります。0 があれば sum(0..r) = prefix[r + 1] − prefix[0] が同じ式からそのまま出てきます。

この方法は符号を気にしません。負の値は累計を少し下げるだけで、引き算は共通部分を正確に打ち消します。最短区間を求めるスライディングウィンドウのレッスンでは、貪欲に区間を縮めるために非負の値を仮定します。固定長のウィンドウにはその制約がなく、累積和も正負が混ざる配列を扱えます。

代償は配列が変わるときに現れます。k > i のすべての prefix[k] は nums[i] を含むので、値を 1 つ変えると後ろの n − i 個がすべて古くなります。次のクエリがこの行を信頼できるようにするには、どれも同じ delta = 新しい値 − 古い値 だけずらす必要があります。

累積和のステップ

既定の入力は nums = [3, 1, 4, -2, 5, 9, 2, 6]、クエリは sum(2..5)、sum(0..7)、sum(4..4)、sum(1..6) の 4 つです。

まずクエリから。 sum(2..5) はいくつでしょう。4、−2、5、9 を順に読むと、 累計は 4 → 2 → 7 → 16。読み取りは 4 回です。続いて sum(0..7) を聞けば、直接足す方法は また走査を始めます。prefix の配列は、この仕事を後のクエリでも再利用できる形で保存します。 冒頭の走査は直接足す方法の実演で、以下の比較は同じ配列への 4 つのクエリを対象にします。

構築。 prefix[0] = 0 から始め、1 ステップに 1 マスずつ足します：

1. prefix[1] = 0 + 3 = 3
2. prefix[2] = 3 + 1 = 4
3. prefix[3] = 4 + 4 = 8
4. prefix[4] = 8 + (−2) = 6。累計が下がりますが、何も壊れません。
5. prefix[5] = 6 + 5 = 11
6. ステップ 6〜8 も同様に続きます：20、22、28。

完成した行は prefix = [0, 3, 4, 8, 6, 11, 20, 22, 28]、足し算 8 回で構築できました。

クエリ。 どのクエリも 2 つの値を読みます：

1. sum(2..5) = prefix[6] − prefix[2] = 20 − 4 = 16。直接足すなら 4 マス読みます。
2. sum(0..7) = prefix[8] − prefix[0] = 28 − 0 = 28。配列全体でも 2 つだけ。ここで先頭の 0 が効きます。
3. sum(4..4) = prefix[5] − prefix[4] = 11 − 6 = 5。1 マスでも 2 つ。
4. sum(1..6) = prefix[7] − prefix[1] = 22 − 3 = 19。6 マスで 2 つ。

各区間を直接足すと 4 + 8 + 1 + 6 = 19 マスを読みます。累積和のクエリが読むのは 8 個で、それに構築時に一度だけ使った 8 回の足し算が加わります。

キャンバスの prefix[k] は区切り k の下にあります。最初の 2 回の足し算は、前の累計と 新しく加える値を一緒に強調します。最初のクエリは右の累計、左の累計の順に読み、共通する マスを打ち消してから答えをしばらく表示します。バーの長さは覆う位置を表し、和の大きさでは ありません。長い区間の和が 0 になることもあります。後のクエリは同じ規則を速く繰り返します。 下の prefix reads は 2 のまま、direct reads は 4、8、1、6 と変わります。

一点更新 シナリオを読み込むと、裏側が見えます。sum(0..5) = 20 のあと、nums[1] が 1 から 7 に変わります（Δ = +6）。prefix[2..8] がすべて古くなり、修復ループが 7 個を 1 つずつ書き直してから、同じクエリをもう一度聞くと 26 が返ります。

時間・空間計算量

空間は n + 1 個の prefix 値で O(n) です。ほとんど変わらない配列に長い区間のクエリを 繰り返すなら、構築のコストを回収できる場合があります。1 マスなら直接 1 回読むだけなので、prefix の 2 回の読み取りが必ず安いわけではありません。変わらない配列に q 回クエリするなら、 全体の時間計算量は O(n + q)。直接足すと最悪 O(n · q) です。

更新が頻繁なら、素朴な累積和配列は向きません。フェニック木（BIT）やセグメント木なら、区間和と一点更新をそれぞれ O(log n) で処理できます。このレッスンが素朴な配列をアニメーションにしているのは、更新のコストを隠さず見せるためです。

境界条件

• 添字 0 から始まる区間。 sum(0..r) = prefix[r + 1] − prefix[0] で、prefix[0] = 0。特別な分岐は不要です。
• 1 マスの区間。 sum(i..i) = prefix[i + 1] − prefix[i] = nums[i]。それでも 2 つ読みます。
• 配列全体。 sum(0..n − 1) = prefix[n]。最後の項目が総和です。
• 負の値。 累計は上がりも下がりもしますが、答えは常に正確です。既定の実行では 8 から 6 に下がります。
• 等しい prefix 値。 prefix[a] = prefix[b] なら、区間 nums[a..b − 1] の和は 0 です。等しい累計 シナリオは 1 つの配列でそうした区間を 3 つ示します。これが「和が k になる部分配列を数える」問題の出発点です。
• 最初または最後の添字の更新。 nums[0] を変えると後ろの n 個すべてを書き直します。nums[n − 1] なら prefix[n] だけです。

よくある間違い

• 両端を含む区間に prefix[r] − prefix[l] を使う。 nums[r] が抜けます。nums[l..r] の右の区切りは r + 1 で、だから累積和配列は n + 1 項目あります。
• 先頭の 0 なしで nums[k] までの和を保存する。 配列が 1 つ短くなり、l = 0 のクエリごとに if が必要になります。off-by-one のバグはその分岐の周りに集まりがちです。
• クエリの中で再構築する。 クエリごとに build(nums) を呼ぶ、あるいはループ内で nums[l:r + 1] を合計すると、1 回あたり O(n) に逆戻りです。一度構築して使い回しましょう。
• 配列がスナップショットであることを忘れる。 nums[i] が変わったら、k > i のすべての prefix[k] は古くなっています。prefix[k] += delta で全部直すか、フェニック木に切り替えます。
• 長い入力でオーバーフローを無視する。 固定幅整数の言語では、どの値も型に収まっていても累計が範囲を超えることがあります。累積和配列にはより広い型を使いましょう。