面内の点を最大化

Question

したがって、基本的には、点よりも厳密に小さい座標を持つ最大値を持つ平面上の点を把握する方法が必要です。

これを実行する1つの方法は、複雑さのあるすべての点をチェックすることです。

O(N) time, N being the number of points. 
O(1) space. 

もう一つの方法は、（バイナリインデックス付き木複雑

O(log(max(X))*log(max(Y)) time, X being the maximum x coordinate and Y being the max y coordinate. 
O(max(X)*max(Y)) space, this is the main problem, I can't afford that much space. 

私は、対数複雑さとOにできるだけ近くを持っている何かをしたいと思います

を与えるだろう（BIT）でそれを行うことであろうN）スペース。

例：各ポイントの

ベストな値は次のとおりです。あなたがしている場合

A -> 0 (none) 
B -> 2 (A) 
C -> 2 (A) 
D -> 0 (none) 
E -> 10 (D) 

Answer 1

は、ここでO（N Nをログ）建設時間（O（N）と、アルゴリズムの野心的であり、空想的なデータ構造の1つを実装する）と、空間およびO（ログN）時間のクエリ。

アイデアは、O（Nログ）時間挿入を有する1D問題に増分溶液を取り、リンクされたWikipediaのページに記載されている標準的な技術を使用して、中央データ構造（平衡二分探索木）partially persistentを作ることです。 2Dデータ構造を構築するには、ポイントをxだけソートしてから1D構造に順番に挿入し、xでソートされたリスト内の1Dスナップショットへの参照を保存します。 2D構造を照会するには、point.x≥query.xのポイントを挿入する前に最後のスナップショットをバイナリ検索してから、1Dクエリを実行します。

y軸の1次元問題を解くために、の非支配のポイントをバランスの取れたバイナリ検索ツリーに保ちます。 （より小さいy値以上の別のポイントがある場合、ポイントが支配されます。）クエリーを実行するには、ツリー内のquery.yの先祖を探します。挿入するには、最初にyを照会して、新しいポイントが支配されていないことを確認します。それが支配的でない場合は、それを挿入し、それを支配した後にポイントを削除します。償却された挿入時間はO（log N）である。