引き算で任意の範囲を合計する
range[l..r] の答えを定数時間で求めます
「引き算で任意の範囲を合計する」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
本当の効果
累積和配列の構築は準備にすぎません。ここからが本番です。たった1回の引き算で、任意の区間和に答えられます。⚡
基本となる考え方
区間和は、大きな合計から小さな合計を1つ引くだけです。2つの累積和の値を引くことで、区間の外側にあるすべての要素をきれいに相殺できます。
公式
l から r までの要素の合計を求めるには、prefix[r + 1] から prefix[l] を引きます。この公式は、どの区間にも使えます。
range_sum = prefix[r + 1] - prefix[l]仕組み
prefix[r + 1] には r までのすべての要素が含まれ、prefix[l] には l より前のすべての要素が含まれます。この差分を取ると、ちょうど中央の区間だけが残ります。
計算例
[3, 1, 4] の prefix は [0, 3, 4, 8] です。インデックス 1 から 2 までの合計を求めるには、8 から 3 を引いて 5 になります。これは 1 と4の合計と一致します。
定数時間のクエリ
各クエリは 1 回の引き算だけで済むため、実行時間はO(1)です。クエリが 1,000 個あっても、1 個あたりのコストは 1 個の場合と変わりません。
オフバイワンに注意
最もよくある間違いは、上端のインデックスです。先頭に 0 を置く場合は、必ず prefix[r] ではなく prefix[r + 1] を使います。この境界を確認してください。
包含と排他
r を含めるかどうかは、早い段階で決めてください。この公式では l と r の両方を含む包含区間として扱います。これは多くの競技プログラミングの問題で想定されています。
関数にまとめる
小さなヘルパー関数にすると、ロジックが読みやすくなり、インデックスの処理も一か所にまとめられます。計算式をその場で書く代わりに、このヘルパーを使ってください。
def query(l, r):
return prefix[r + 1] - prefix[l]配列全体を処理する
配列全体の合計を求めるには、l を 0、r を n - 1 としてクエリします。公式から prefix[n] が得られ、これが総合計になります。
効果を発揮する場面
固定された配列に対して大量の区間合計クエリを処理する問題では、累積和によってクエリごとの O(n) のループを即時に答えられる処理へ変えられます。
確認問題
インデックス l から r までを含む範囲の合計を求めます。
まとめ
prefix[r + 1] から prefix[l] を引けば、任意の区間の合計をO(1)で求められます。先頭に 0 を置いたことによるずれに注意すれば、バグなく実装できます。✅
よくある質問
「引き算で任意の範囲を合計する」レッスンは無料ですか？
はい。「引き算で任意の範囲を合計する」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「引き算で任意の範囲を合計する」で何を学びますか？
range[l..r] の答えを定数時間で求めます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「引き算で任意の範囲を合計する」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 累積和配列を構築する
- 引き算で任意の範囲を合計する
- 目標の合計を持つ部分配列を数える
- 区間更新のための差分配列