Counting Inversions Using BIT

Question

I know this question was discussed earlier, but I'm interested in this using a binary indexed tree. I found this link to show how to do this. I did not quite follow the explanation. Can someone please give me an explanation of why the following 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) (ie add 1 to the position A[j] on BIT. This effectively counts the number of time value A[j] is seen so far) 

I do not understand why this works.

Answer 1

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

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

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

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

We effectively execute the count by moving the array from left to right and always tracking how many elements of each value have been found so far using BIT. Initially, our frequency table will be [0, 0, 0, 0], since we did not see any elements at all. After visit 4, we update its frequency, giving [0, 0, 0, 1]. After visiting 3, [0, 0, 1, 1], etc.

Every time we visit a position, we use BIT to find out how many impressions of elements are greater than this. So, for example, when we encounter 1, BIT currently contains [0, 0, 1, 1], representing that there were still zero 1 and 2, one 3 and one 4. Adding the values ​​0 + 1 + 1 , we count the number of elements so far that are greater than 1.

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

Please note that in general, you should use coordinate compression to be effective. For example, if your starting array contains numbers, such as A = [92, 631, 50, 7], you should not allocate BIT with hundreds of elements. Instead, sort the array to determine that 7 <50 <92 <631, which allows you to assign ranks 7 => 1, 50 => 2, 92 => 3, 631 => 4; then replace each element with 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 is likely to use indexes starting at zero.)