左にあり、要素より大きい配列の数値を数える

Question

この問題の助けが必要で、N要素の配列を与えました。すべてのインデックスに対して、どれだけ多くの要素を保持するか新しい配列を生成したい数字はこのインデックスの左側にあり、この要素よりも大きいです。

この配列{3,2,1,0}があり、この配列{0,1,2,3}を生成したいとしましょう。 2番目の配列では、要素3の左に要素がないためゼロがあります。番号3が2の左にあり、それが大きいために1があります。

これはバイナリインデックスツリー、しかし私はそれを実装する方法を知らない。

ありがとうございます。

Answer 1

NlogNでこれを行うには、バイナリツリーを構築し、途中のノードにいくつかのメタデータ、つまり各ノードの右側のサブツリーの現在のサイズを保存します。各要素が追加された後、以前にツリーに追加された要素の数よりも大きな要素の数を数えます。ノードを1つずつ挿入してバイナリ検索ツリーを作成する方法を知っていると仮定します。

各ノードの右のサブツリーのサイズを維持します。現在の値が右側のサブツリーにある場合、各ノードで選択します（現在の値は、現在の値よりも大きくなります）。ノード値）または左のサブツリー。右に行くことを選択した場合は、rightSubtreeSizeの値を1だけ増やします。

以前に挿入された要素の数が現在の要素よりも多いかを調べる：各ノードについて、正しいサブツリーのサイズを知っていると仮定して、現在の要素の左側にある要素の数（つまり、左の要素は既にツリーに追加されています）。ここでも、バイナリツリーの挿入操作に従います。各ノードで、現在の値がノードよりも小さい場合は、そのノードとその右端のサブツリーが現在の値よりも大きいことを意味します。トラバースするノードごとに、現在の値より大きいすべての要素の合計を保持します。ツリーへの挿入が完了するまでに、私たちが探している合計があります。

説明が必要な場合はお知らせください。