ゲームのスコアランキングを考えます。各ユーザーに対して、スコアがただ一つ紐づいているとします。このとき、あるユーザーが与えられた時、全ユーザーの中で何番目のスコアを持っているかを知りたいとします。

このようなランキングのデータ構造は、取得と更新の計算量がトレードオフの関係にあると思います。

というのも、例えば各ユーザスコアデータについて、愚直にユーザーをキーにしたハッシュテーブルに入れておき、取得のタイミングで全テーブルを検索して、自分よりも大きなスコアを持つ要素をかぞえあげるとします。その場合、計算量は以下になります。

  • 更新系: O(1) ※hash index であった場合
  • 取得系: O(N)

また逆に、すべてのユーザーについてランキングをあらかじめ計算しておくとします。その場合、愚直に考えれば、全ての要素について見ていって、更新ユーザーの更新前と後の間の値のユーザースコアを持つユーザーのランクを、+/- 1 していくことで、更新できます。この場合、計算量は以下です。

  • 更新系: O(N)
  • 取得系: O(1) ※ hash index であった場合

質問

ランキングをデータ上に保持するとして、その取得系と更新系の計算量のうち、最悪の方について常に着目する場合、それはどこまで最小化できますか？