It is simple. Initialize BIT[MAXN+1] to zero. 1.Iterate from Right to left 2.For each element array[i] Check how many elements are smaller than array[i]. This can be done by just a simple query(array[i]-1); 3. Update the array[i]th index in BIT by 1. // Simple code snippet. long ans=0; For(int i=sz-1;i>=0;i--){ ans+=query(array[i]-1); update(array[i],1); }
You are consider the array element as indices of BIT so make sure u have mapped all the elements of the array from 1 to MAXN which can be done by sorting the input and using c++ stl maps. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.