algorithm - 配列内の各位置の左側にある個別の小さい要素の数

Question

配列内の各位置の要素よりも左にある個別の要素の数を見つけるという問題に出くわしました。

例：

配列1 1 2 4 5 3 6の場合、答えは次のようになります0 0 1 2 3 2 5

^{O(n 2} ) で問題を解決するのは簡単です。問題が O(n*lg(n)) で解決できるかどうか知りたいです。

Answer 1

はい、バランスの取れた（赤黒、AVGなど）バイナリ検索ツリーに要素を挿入するだけで、各ノードにサブツリーノードの合計数を保存できます。ルートへのパスに沿ってのみ更新するため、更新は O(log N) であり、個別の要素の数のチェックも O(log N) です。新しい要素から根。

これは、[0,1,2,3,5,6] (括弧内のサブツリーのノード数) を挿入した後のツリーの外観です。

    2(6)
   /  \
  1(2) 5(3)
 /    / \
0(1) 3(1)6(1)

6 を挿入するときに (最後と仮定して)、以下を追加します。

• 2 (左側のサブツリーのノード数 2)
• 1 (2 のノード。正しいパスを使用するため、ルートは小さくなります)
• 1 (5 の左部分木)
• 1 (5 のノード、同じ理由、追加する左サブツリーなし)

合計 5。ツリーは小さすぎて、合計を維持することによる節約を確認できませんが、0 ノードにアクセスする必要はないことに注意してください。これは、その親である 1 ノードで説明されています。