SPOJ PROBLEM 6256 :INVERSION COUNT (INVCNT)

Problem link : http://www.spoj.com/problems/INVCNT/
 
Done it using Fenwick Tree !!!!

Took a time as well as resources to get through the logic...

Let array    A[5] =   2        3      8        6         1
                           
Let fenwick tree be F[maxvalue(a)=8]= 
0 0 0 0 0 0 0 0 0
So,
Inserting 2 in it ;  
0 1 0 0 0 0 0 0 0          count=0;
Inserting 3 in it ;
0 1 1 0 0 0 0 0 0          count=0;
Inserting 8 in it ;
0 1 1 0 0 0 0 0 1          count=0;
Inserting 6 in it ;
0 1 1 0 0 0 1 0 1          count=1;
Inserting 1 in it ;
1 1 1 0 0 0 1 0 1          count=1+4;

Basic logic is to get through that after inserting each number we have to count number of indexes marked with 1 after it ( That's what the problem says i<j  A[i]>A[j]  )
 Or Simply:
Sum of fenwick tree after number i.e. sum[num+1........MAX]

Don't forget to take tree size >=1e7  and total count of inversions as long long :P