O(N log(N)) の前処理時間と O(N log(N)) の余分なスペースを考えると、O(log(N)) 時間でアクセスを実行できると思います。方法は次のとおりです。
赤黒木を拡張して、O(log(N)) 時間select(i)
でランクの要素を取得する操作をサポートできます。i
たとえば、この PDFまたはIntroduction to Algorithmsの該当する章を参照してください。
select(i)
挿入操作が O(log(N)) 個を除くすべてのノードを古いツリーと共有する新しいツリーを返すように、機能的な方法で赤黒ツリー ( をサポートするように拡張されたものでも) を実装できます。たとえば、Chris Okasaki によるPurely Functional Data Structuresを参照してください。
ツリーが最大から最小にソートされた最初の要素のインデックスを格納するT
ように、純粋に機能的な拡張赤黒ツリーの配列を構築します。T[j]
0 ... j-1
j
A
基本ケース: T[0]
1 つのノードのみを持つ拡張赤黒ツリーを作成します。そのデータは、配列の最初の 1 要素の中で 0 番目に大きい要素のインデックスである番号 0A
です。
帰納的ステップ: j
1 から までのそれぞれについて、インデックス付きの新しいノードをツリー に純粋に機能的に挿入することにより、増補赤黒ツリーを作成N-1
します。これにより、最大で O(log(j)) 個の新しいノードが作成されます。残りのノードは と共有されます。これには O(log(j)) 時間がかかります。T[j]
j
T[j-1]
T[j-1]
配列を構築するための合計時間T
は O(N log(N)) であり、使用される合計スペースも O(N log(N)) です。
が作成されると、 を実行することにより、 の最初の要素T[j-1]
の th 番目に大きい要素にアクセスできます。これには O(log(j)) 時間がかかります。初めて必要になったときに遅延作成できることに注意してください。が非常に大きく、常に比較的小さい場合は、時間とスペースを大幅に節約できます。i
j
A
T[j-1].select(i)
T[j-1]
A
j