※有料会員になるとこの動画をご利用いただけます
詳しい説明を読む
＃05:並列二分探索
このチャプターでは、複数の二分探索を高速に処理する並列二分探索について学習します。
・二分探索の情報を次の中間値の時刻ごとに管理
・クエリがなくなるまで以下の処理を繰り返す
・1. シミュレーションを初期化
・2. 時刻 t = 0 ~ T まで以下の処理をおこなう
・2.1. 中間値が時刻 t のクエリをすべて更新※
・2.2. t < T ならシミュレーションを 1 つ進める
※二分探索の左右判定と更新をおこなった後、次のループ用のデータ構造に、次の中間値の時刻をキーにしてクエリを追加。ただし、終了条件を満たした場合は追加せず、答えを保存する。
・補足：クエリが先読みできない場合（オンラインクエリ）は、並列二分探索のアルゴリズムを使うことができない。しかし、そのような場合でも永続データ構造と呼ばれるデータ構造を用いることで複数の二分探索を高速に処理できることがある。
・このアルゴリズムの実装はかなり複雑なので、このチャプターの演習問題はありません。しかし、腕に自信があるかたは、以下の問題に挑戦してみるとよいでしょう。
・https://paiza.jp/works/mondai/binary_search_related/binary_search_related__related_algorithms_3/