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

概要

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

アルゴリズム

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

追加

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

取得

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