累積和配列を構築する
累積合計を一度だけ前計算します
「累積和配列を構築する」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
繰り返し行う合計の問題
1つの配列に対して、何百回も区間和を求める場面を考えてみましょう。各区間を毎回最初から合計すると遅くなります。これを解決するのが 累積和です。🚀
累積和とは
累積和配列には、各インデックスまでのすべての要素の合計を、それぞれの位置に保存します。事前計算を1回行うだけで、遅い合計処理を即座に答えられる処理へ変えられます。
小さな例
[3, 1, 4] の場合、途中の合計は3、次に4、最後に8です。この増えていく合計のリストが、まさに累積和です。
基本となる漸化式
各要素は、1つ前の合計に現在の要素を加えたものです。この1行の漸化式が、技法全体の中心になります。
prefix[i] = prefix[i - 1] + a[i]コードで構築する
配列を1回走査し、途中の合計を保持します。各ステップで新しい合計を追加するため、配列の構築は1回の線形走査で完了します。
prefix = [0]
for x in a:
prefix.append(prefix[-1] + x)先頭に0を置く利点
累積和の先頭に0を置くと、prefix[i] が最初の i 個の要素の合計を保持する形になります。これにより、後で区間の計算を簡潔にできます。
インデックスの規則
先頭に0を置く場合、prefix[k] は a[0] + ... + a[k-1] と等しくなります。この規則を正しく保つことで、厄介な off-by-one バグを防げます。
構築にかかるコスト
累積和配列の構築では各要素に1回ずつ触れるため、時間計算量は O(n) です。このコストは1回だけ支払い、その後は何度でも再利用できます。
1回前計算して何度も問い合わせる
大きな利点は、このトレードオフです。最初に1回の線形走査を行うことで、その後の合計の問い合わせをループではなく高速な参照にできます。
Pythonらしい短縮方法
標準ライブラリを使えば、合計を自動的に構築できます。itertools.accumulate は、途中の合計を1回の簡潔な呼び出しで生成します。
from itertools import accumulate
prefix = [0] + list(accumulate(a))メモリに注意する
累積和配列の長さは、入力と同じ長さに1を加えたものです。入力が非常に大きい場合は、メモリ使用量が倍増することを覚えておいてください。
確認問題
累積和配列を構築します。通常、インデックス0には何が入りますか。
まとめ
先頭に0を置き、1回の O(n) の走査で累積和配列を構築する方法を学びました。1回前計算して、その後は再利用します。✅
よくある質問
「累積和配列を構築する」レッスンは無料ですか？
はい。「累積和配列を構築する」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「累積和配列を構築する」で何を学びますか？
累積合計を一度だけ前計算します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「累積和配列を構築する」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。