0Pricing
Coding Interview Prep · レッスン

区間更新のための差分配列

範囲への加算操作を多数、高速に適用します

「区間更新のための差分配列」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

問題を反転する

累積和によって区間クエリを高速に処理できました。差分配列はその逆に、多数の区間更新を高速に適用します。🔁

遅い方法

区間内のすべての要素に値を加える処理を何度も繰り返すと、更新 1 回につき O(n) かかります。q 回の更新では、そのコストが大きく膨らみます。

変更箇所だけを記録する

すべての要素に触れる代わりに、変更が始まる位置と終わる位置だけを記録します。中央ではなく、両端に印を付けるのです。

差分配列に保存されるもの

差分配列には、各要素とその直前の要素との差が保存されます。1 つの差分を編集すると、その後の広い範囲をまとめて変化させられます。

2 つの印を付ける方法

l から r までに v を加えるには、インデックス l に v を加え、インデックス r + 1 から v を引きます。たった 2 回の編集で範囲全体を扱えます。

diff[l] += v
diff[r + 1] -= v

引き算を行う理由

l での加算によって変更を有効にし、r + 1 での減算によって再び無効にします。これらを組み合わせることで、更新を 1 つの範囲に限定できます。

すべての更新を安く適用する

更新 1 回につき配列への書き込みは 2 回だけなので、q 回の更新は合計O(q)で済みます。重い処理は最後まで先送りされます。

最終配列を復元する

すべての印を付け終えたら、差分配列の累積和を求めます。この 1 回の走査で、最終的なすべての値を復元できます。

for i in range(1, n):
    diff[i] += diff[i - 1]

番兵用の領域を確保する

配列を 1 要素分長くして、r + 1 が末尾からはみ出さないようにします。この余分な番兵用の領域により、インデックスエラーを防げます。

全体のコスト

更新の記録に O(q)、復元の走査に O(n) かかります。合計のコストは、単純な O(n × q) より大幅に小さくなります。

効果を発揮する場面

差分配列は、予約数の集計や道路料金、その他多数の区間加算を行って最後に 1 回だけ読み取る問題で力を発揮します。

確認問題

インデックス l から r までのすべての要素に v を加えます。

まとめ

差分配列を使えば、区間更新をまとめて処理できます。l と r + 1 に印を付け、最後に 1 回だけ累積和を求めて復元します。更新は高速で、読み取りは 1 回です。✅

よくある質問

「区間更新のための差分配列」レッスンは無料ですか？

はい。「区間更新のための差分配列」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「区間更新のための差分配列」で何を学びますか？

範囲への加算操作を多数、高速に適用します ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。

「区間更新のための差分配列」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 累積和配列を構築する
  2. 引き算で任意の範囲を合計する
  3. 目標の合計を持つ部分配列を数える
  4. 区間更新のための差分配列
← Coding Interview Prepに戻る