Following is the code for counting number of inversions in a permutation(1...n) using fenwick tree. I can't get "inv += query(n) — query(a[i]); update(a[i], 1);" these two steps. Can anyone help?
include <bits/stdc++.h>
using namespace std; long long bit[1000005],a[1000005],n;
void update(int x,int del) { for(;x<=n;x+=x&-x) { bit[x]+=del; } } int query(int x) { int sum=0; for(;x>0;x-=x&-x) { sum+=bit[x]; } return sum; } int main() { cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}long long inv = 0; for (int i=1; i<=n; i++) { inv += query(n) — query(a[i]); update(a[i], 1); } cout<<inv<<endl; return 0; }
It's important that you first understand the quadratic method for counting inversions. For each element, look at all the previous elements and count the number that are greater than the current element. Add this to your answer.
So, we are using the Fenwick tree to keep track of what numbers we have seen already, where a 1 indicates seen, and 0 indicates not seen. At each element, we can tell the number of greater elements that came before it by querying the sum of the range a[i] to n. This is the first line you referenced. Then, we want to say that we've seen a[i], so we update that to 1 and continue for the rest of the array.