使用位計數倒數

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

當元素大於數組中的某個元素時發生反轉。

我們可以通過按第二個元素對它們進行分組來計數倒數。例如，在數組[4,3,1,2]中，元素對（4,3），（4,1），（4,2），（3,1）和（3,2）是倒置。我們按第二個元素對它們進行分組，因此：[[（4,1），（3,1）]，[（4,2），（3,2）]，[（4,3）]]。

我們依次考慮每個元素，並計算它是第二個元素的反轉次數。在該例子中，元素4是0倒數的第二元素，3倒數的元素3，以及每個元素1和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.通過將值0 + 1 + 1 ，我們計算到目前爲止大於1的元素數量。

添加全部這些個體計數給出了反轉的總數。

請注意，一般來說，您必須採用座標壓縮以使其高效。例如，如果您的初始數組包含像A = [92,631,50,7]這樣的數字，則不應該爲數百個元素分配一個BIT。相反，對數組進行排序以確定這允許我們分配秩7 => 1,50 => 2,92 => 3,631 => 4;然後用它的等級替換每個元素，給出B = [3,4,2,1]。由於B [i]> B [j]當且僅當A [i]> A [j]，這個數組的反轉次數將與原始數據相同。

（注意：真正的程序員可能會使用從零開始的索引。）