私はこの質問が以前に議論されたことを知っていますが、私はバイナリインデックスツリーを使用してこれを行うことに興味があります。私はそれを行う方法を示すためにこのリンクを見つけました。私は説明に完全には従いませんでした。誰かが私に次のことが真実である理由を説明してもらえますか？
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)
なぜこれが機能するのかわかりません。
反転は、要素が配列内でそれに続く要素よりも大きい場合に発生します。
2番目の要素でグループ化することにより、反転をカウントできます。たとえば、配列[4、3、1、2]では、要素のペア（4、3）、（4、1）、（4、2）、（3、1）、および（3、2）は次のようになります。反転。それらを2番目の要素でグループ化します。つまり、[[（4、1）、（3、1）]、[（4、2）、（3、2）]、[（4、3）]]です。
各要素を順番に検討し、それがの2番目の要素である反転の数を数えます。この例では、要素4は0反転の2番目の要素、要素3は1反転、要素1と2はそれぞれ2反転です。
任意の要素が反転の2番目の要素になるためには、配列内のその前のどこかに大きな要素が存在する必要があります。
配列を左から右にトラバースし、BITを使用して、これまでに検出された各値の要素の数を常に追跡することにより、カウントを効率的に実行します。要素がまったく表示されていないため、最初は度数分布表は[0、0、0、0]になります。4にアクセスした後、その頻度を更新して、[0、0、0、1]を指定します。3、[0、0、1、1]などにアクセスした後。
ポジションを訪問するたびに、BITを使用して、これまでに訪問した要素の数がそれよりも多いかどうかを調べます。したがって、たとえば1に遭遇すると、BITには現在[0、0、1、1]が含まれ、これまでに1と2がゼロ、3と4が1つあったことを表します。値0 + 1+1を追加することによって、これまでに1より大きい要素の数を数えます。
これらすべての個別のカウントを加算すると、反転の総数が得られます。
一般に、これを効率的にするには、座標圧縮を使用する必要があることに注意してください。たとえば、最初の配列にA = [92、631、50、7]のような数値が含まれている場合、数百の要素を含むBITを割り当てないでください。代わりに、配列を並べ替えて7 <50 <92 <631と判断します。これにより、ランク7 => 1、50 => 2、92 => 3、631=>4を割り当てることができます。次に、各要素をそのランクに置き換えて、B = [3、4、2、1]にします。A [i]> A [j]の場合に限り、B [i]> B [j]であるため、この配列の反転回数は元の配列と同じになります。
（注：実際のプログラマーは、おそらくゼロから始まるインデックスを使用します。）