noshi91のメモ

データ構造のある風景

(計算量 k 倍) 上位 k 個を取得する Li Chao Tree

概要

  • Li Chao Tree で小さいほうから  k 個取得できる
  • ただし取り出した  k 個の順番は保証されない
  • 空間計算量  \Theta ( k n )
  • 時間計算量  \Theta ( k \log ( n ) ) per query


アルゴリズム

全てのノードは高々  2 k - 1 個の直線を保持します。 元の Li Chao Tree と同様、クエリの点を覆うノードの直線だけでクエリが処理できる状態を維持します。

追加

ノードに直線を追加することを考えます。 元々入っていた直線が  2 k - 1 本未満なら、ただ追加して終わります。 そうでない場合、新しい直線と合わせて  2 k 本の直線があります。 これらのうち、ノードの中央の点での値が最も大きいものを  l とします。
 l と他の直線を比較すると、 l は左と右の少なくとも一方の区間では完全に大きいです。  l 以外に  2 k - 1 個の直線があるため、左と右のどちらかでは  k 個以上の直線に対して  l は大きくなります。 よってそちら側の区間 l は上位  k 個になり得ず、反対側の区間再帰的に  l を追加すればよいです。

f:id:noshi91:20191211210528j:plain

取得

クエリの点を覆う全てのノードの直線を列挙した後、選択アルゴリズムで上位  k 個を取り出します。