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.