BITを使用して反転をカウントする

Question

この質問は前に説明したことがわかりましたが、私はバイナリインデックス付きツリーを使用してこれを行うことに興味があります。私はそれを行う方法を示すために thisリンクを見つけました。私は説明にかなり従っていませんでした。誰かが私になぜ以下のことが当てはまるのか説明してください。

Create a BIT of size greater than n(no of elements). Iterate through array A (
let j be the index of loop),and for each element A[j] do: 

1) Add j-sum(A[j]) to the number of inversions 
2) add(A[j], 1) (i.e. add 1 to the position A[j] on BIT. This effectively 
counts the number of time value A[j] is seen so far) 

これはなぜ機能しないのですか。

Answer 1

要素内の要素が配列内の要素よりも大きい場合は、逆転が発生します。

逆転は、2番目の要素でグループ化することでカウントできます。例えば、配列[4,3,1,2]では、要素対（4,3）、（4,1）、（4,2）、（3,1）、（3,2）は逆転。したがって、[[（4,1）、（3,1）]、[（4,2）、（3,2）]、[（4,3）]]という2番目の要素でグループ化します。

各要素を順番に考え、2番目の要素の逆数を数えます。この例では、要素4は0反転の2番目の要素、1の反転3要素、2反転の要素1と2です。

任意の要素が反転の2番目の要素であるためには、配列の前のどこかに大きな要素が存在する必要があります。

BITを使用して、配列を左から右に横断し、これまでに各値のいくつの要素が遭遇したかを常に追跡することによって、効率的にカウントを実行します。初期には、要素がまったく見つからなかったので、頻度表は[0、0、0、0]になります。我々が4を訪れた後、我々はその頻度を更新し、[0、0、0、1]を与える。 3、[0、0、1、1]、などを訪問した後。

私たちはある位置を訪れるたびに、これまで訪問した要素の数がBITを超えているかどうかを調べます。たとえば、1に遭遇したときに、BITは現在、0と1と2と1と3と1とが存在することを表す[0、0、1、1]を含む。値0 + 1 + 1これまでの要素の数を1より大きい数に数えます。

をすべて追加します。これらの個々の数は、逆数の合計数を示します。

これが効率的であるためには、一般に座標圧縮を使用する必要があります。たとえば、初期配列にA = [92,631,50,7]のような数値が含まれている場合は、数百の要素でBITを割り当てるべきではありません。代わりに、配列をソートして、7 => 1,50 => 2,92 => 3,631 => 4のランクを割り当てることができることを決定するために配列をソートします。各要素をランクで置き換えて、B = [3、4、2、1]とする。この配列の逆数は、A [i]> A [j]の場合にのみB [i]> B [j]であるため、元のものと同じになります。

（注：実際のプログラマーはおそらくゼロから始まるインデックスを使用するでしょう）