使用位计数反演 [英] Counting Inversions using BIT

问题描述

我知道这个问题已经讨论过，但我感兴趣的使用二进制索引树这样做。我发现<一href="http://www.quora.com/Algorithms/How-can-I-efficiently-compute-the-number-of-swaps-required-by-slow-sorting-methods-like-insertion-sort-and-bubble-sort-to-sort-a-given-array"相对=nofollow>这个链接显示怎么办吧。我不太明白的解释。可能有人请给我的，为什么下面给有真实的解释。

 创建大小大于n（无元素）的BIT。通过数组A迭代（
J为一个循环的指标），以及每个元素的研究[J]这样做：

1）加入J-SUM（A [J]），以反转的数目
2）加（A [J]，1）（即加1 ON位的位置A [J]。这有效地
计数时间值A [J]的数量被认为是到目前为止）
 

我不明白为什么这个工程。

解决方案

当一个元素是比它后面的数组中某些元素出现较大反转。

我们可以通过第二个元素将它们分组数反转。例如，阵列[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是在每个2反转所述第二元件在0反转，在1反转的元件3，和元件1和2。

为了对于任何给定元件是一个倒置的第二元件，必须有一个较大的元件某处之前它的阵列中。

我们通过遍历阵列从左至右和始终跟踪如何每个值的许多元​​件已经遇到到目前为止，使用BIT有效地进行计数。最初，我们的频率表将是[0，0，0，0]，因为我们已经看到任何元素都没有。之后，我们参观了4，我们更新它的频率，从而[0，0，0，1]。来访后3，[0，0，1，1]，等等。

每次我们访问一个位置，我们用了一下，找到了多少个访问元素至今都大于它。因此，例如，当我们遇到1，BIT中当前包含[0，0，1，1]，重新presenting，有迄今零1和2的，1 3，以及一个4.通过将值0 + 1 + 1，我们计数元件的数目迄今是大于1

添加的所有的这些个体数给出了反转的总数。

需要注意的是，在一般情况下，你必须使用的协调COM pression 的，以便为这是有效的。例如，如果您最初的数组包含如A = [92，631，50，7]，你不应该有数百要素分配位数。相反，对数组进行排序，以确定7＆LT; 50℃ 92＆LT; 631，这使我们能够分配的行列7 => 1，50 => 2，92 => 3，631 => 4;然后，通过它的秩替换每个元件，给B = [3,4，2，1]。这个阵列的反转的数目将是一样的，在原始的，由于B [Ⅰ]>乙[j]的当且仅当A [1]> A [j]的

（注：一个真正的程序员可能会使用索引从零开始）

I know this question has been discussed before, but i am interested in doing this using a Binary Indexed Tree. I found this link to show how to do it.I did not quite follow the explanation. Could someone please give me an explanation of why the following given there is true.

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)

I dont get why this works.

解决方案

An inversion occurs when an element is larger than some element that follows it in the array.

We can count inversions by grouping them by second element. For example, in the array [4, 3, 1, 2], the element pairs (4, 3), (4, 1), (4, 2), (3, 1), and (3, 2) are inversions. We group them by second element, hence: [[(4, 1), (3, 1)], [(4, 2), (3, 2)], [(4, 3)]].

We consider each element in turn, and count how many inversions it is the second element of. In the example, the element 4 is the second element in 0 inversions, the element 3 in 1 inversion, and the elements 1 and 2 in 2 inversions each.

In order for any given element to be the second element of an inversion, there has to be a larger element somewhere before it in the array.

We perform the count efficiently by traversing the array from left to right and always keeping track of how many elements of each value have been encountered so far, using a BIT. Initially our frequency table will be [0, 0, 0, 0], since we've seen no elements at all. After we visit the 4, we update its frequency, giving [0, 0, 0, 1]. After visiting the 3, [0, 0, 1, 1], and so on.

Each time we visit a position, we use the BIT to find out how many elements visited so far are greater than it. So for example when we encounter the 1, the BIT currently contains [0, 0, 1, 1], representing that there were so far zero 1's and 2's, one 3, and one 4. By adding the values 0 + 1 + 1, we count the number of elements so far that are greater than 1.

Adding all these individual counts gives the total number of inversions.

Note that, in general, you must employ coordinate compression in order for this to be efficient. For example, if your initial array contains numbers like A = [92, 631, 50, 7], you shouldn't allocate a BIT with hundreds of elements. Instead, sort the array to determine that 7 < 50 < 92 < 631, which allows us to assign the ranks 7 => 1, 50 => 2, 92 => 3, 631 => 4; then replace each element by its rank, giving B = [3, 4, 2, 1]. The number of inversions of this array will be the same as in the original, since B[i] > B[j] if and only if A[i] > A[j].

(Note: A real programmer would probably use indices starting from zero.)

这篇关于使用位计数反演的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！