CODEWITHSUNDEEP
c++algorithmtree
Rainier1
Rainier1

Reputation: 71

Difficulty understanding code to count the number of inversions using BIT

Here is the code:

#include<iostream>
using namespace std;

const int MX = 100;
int n,a[MX*2],bit[MX];

void add(int x, int y){
    for(;x<=n; x+=-x&x) bit[x]+=y;
}
int query(int x){
    int s= 0;
    for(;x>0; x-=-x&x) s+=bit[x];
    return s;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int ans = 0;
    cin >> n; n*=2;
    for(int i = 0; i<n; i++){
        cin >> a[i];
    }
    for(int i = n-1; ~i; i--){
        ans+=query(a[i]-1);
        add(a[i],1);
    }
    cout << ans;
}

I dont understand how the query and add contribute to finding the number of inversions in an array. If someone can help explain this to me that would be great. Thanks.

Upvotes: 0

Views: 55

Answers (1)

srt1104
srt1104

Reputation: 959

Firstly, I hope you understand how add and query work in BIT. If not, think of BIT like a blackbox which stores prefix sums for count of elements 1, 2, ..., n in array A. For example, A[3] = count(1) + count(2) + count(3). add(x, y) increments count(x) by y and query(x) returns the sum count(1) + count(2) + ... + count(x) i.e., the prefix sum till element x.

Elements at index i and j form an inversion if i < j and arr[i] > arr[j]. But the above code reads it the other way; j > i and arr[j] < arr[i] (this save an extra call to query).

Now suppose the array is {3, 4, 1, 5, 2} and {2, 5, 1} have already been inserted in the BIT. Then query(1) = 1, query(2) = 2, query(3) = 2, query(4) = 2 and query(5) = 3 (remember to think of BIT as a blackbox that stores prefix sums). Notice when index i is pointing at element 4, all the elements that have already been inserted having indices j1, j2, ..., jk are all > i so now we only need to count the number of elements < 4 which is the prefix sum till 3 which we get by calling query(3).

Upvotes: 1

Related Questions