Assuming you know how to solve the following problem in O(log n) for each request and update using BIT:
Given an array A[1 .. n], implement the following functions efficiently: query(x, y) = return A[x] + A[x+1] + ... + A[y] update(x, v) = set A[x] = v
You can solve your current problem as follows: first, normalize the values of the array. This means that you must convert all your values so that they are in the interval [1, n] . You can do it with a kind. For example, 5, 2, 8 will become 2, 1, 3 . (Note: 1, 2, 3 - indexes in sorted order 5, 2, 8)
Then for each i we will answer how many inversions A[i] generated with elements j < i . To do this, we need to find the number of elements up to i that are greater than i . This is equivalent to query(A[i] + 1, n) .
After this request we do update(A[i], 1) .
Here's how it works: our BIT array will initially be filled with zeros. A 1 at position k in this array means that we met the value of k in our iteration over this array. By calling query(A[i] + 1, n) , we find how many inversions A[i] generated along with the elements in front of it, because we ask how many elements are more than we have repeated so far.
After that, we need to mark A[i] as visited. We do this by updating the position of A[i] in our BIT array and putting 1: update(A[i], 1) .
Since the numbers in the array differ from 1 to n , your BIT array is of size n , and the complexity is logarithmic to n .
Please write if you want to get detailed information on how to solve the initial problem, although this is a classic, and you should be able to easily find the code on Google.
Note. the problem also has a great solution using merge sort , which you might think about.