(計算量 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$ を追加すればよいです。