範囲更新の遅延伝播
範囲全体への更新を後回しにします
「範囲更新の遅延伝播」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
区間更新の問題
「l から r までのすべての要素に 5 を加える」というクエリが来たらどうでしょうか。各葉に触れると更新1回あたり O(n) かかり、多数の区間更新には遅すぎます。😰
遅延の考え方
遅延伝播を使うと、ノードは保留中の変更を、すぐには子へ伝えずに覚えておけます。実際に子が必要になるまで処理を先送りする仕組みです。
保留中の処理用の第2配列
木と並べてlazy配列を保持します。lazy[node] には、そのノード全体の区間に適用されるものの、まだ下へ伝播していない更新を格納します。
lazy = [0] * (4 * n)ノード全体に適用する
更新がノード全体を覆う場合は、格納された値を調整し、変更をlazyに積んでから終了します。下の階層へ進む必要はありません。
seg[node] += (r - l + 1) * val
lazy[node] += val下へ進む前に伝播する
子を調べる前に、保留中の lazy の値を両方の子へpush downします。これにより、子を読み取る時点で常に正しい状態になります。
def push_down(node, l, r):
if lazy[node]:
apply(2*node, l, mid)
apply(2*node+1, mid+1, r)
lazy[node] = 0ノードごとの3つのケース
各ノードで、クエリ区間は重ならない、完全に覆う、部分的に重なる、のいずれかです。それぞれ、スキップ、遅延適用、両方の区間への再帰を行います。
遅延更新も対数時間
区間更新では、完全に覆われたノードが早期終了するため、触れるノードは O(log n) 個だけです。これが遅延伝播を使う大きな利点です。⚡
クエリでもプッシュダウンする
区間クエリでも、再帰する前に必ずプッシュダウンして、子ノードの最新の値を読み取れるようにする必要があります。これを忘れるのは、遅延伝播でよくある典型的なバグです。
再帰後にプルアップする
子ノードを更新したら、子ノードの値から親ノードを再計算します。このプルアップにより、すべての内部ノードとその部分木の整合性が保たれます。
seg[node] = seg[2*node] + seg[2*node+1]代入と加算
遅延伝播は多くの演算で使えますが、代入と加算では結合方法が異なります。実装する前に、保留中の2つの更新をどのように統合するか決めておきましょう。
遅延伝播を使うべき場面
遅延伝播を使うのは、本当に区間更新が必要な場合だけにしましょう。点更新だけなら、通常のセグメント木のほうが単純で十分です。
理解度チェック
ノードの子に再帰する前に、何を行う必要がありますか？
まとめ: 遅延更新
遅延伝播について学びました。保留中の変更を保存し、下へ進む前にプッシュダウンし、その後にプルアップすることで、O(log n) の区間更新を実現できます。🎉
よくある質問
「範囲更新の遅延伝播」レッスンは無料ですか？
はい。「範囲更新の遅延伝播」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと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フィードバックを取得できます。ローカル設定は不要です。