Inversion Count by BIT

For Theory Part

#include<bits/stdc++.h>

#define N 10000007

#define ll long long

using namespace std;

int a[N], tree[N];

int query(int indx)

{

    int sum = 0;

    while(indx > 0)

    {

        sum += tree[indx];

        indx = indx - (indx & (-indx));

    }

    return sum;

}

void update(int indx, int value, int n)

{

    while(indx <= n)

    {

        tree[indx] += value;

        indx = indx + (indx & (-indx));

    }

}

void convert(int n)

{

    int temp[n];

    for(int i=0; i<n; i++)

        temp[i] = a[i];

    sort(temp, temp+n);

    for(int i=0; i<n; i++)

    {

        int low = 0, heights = n-1, m;

        while(low <= heights)

        {

            m = (low + heights)/2;

            if(a[i] == temp[m])

                break;

            else if(a[i] < temp[m])

                heights = m-1;

            else

                low = m+1;

        }

        a[i] = m+1;

    }

}

int invcnt(int n)

{

    convert(n);

    int cnt = 0;

    for(int i=n-1; i>=0; i--)

    {

        cnt += query(a[i] - 1);

        update(a[i], 1, n);

    }

    return cnt;

}

int main()

{

    int n;

    cin >> n;

    for(int i=0; i<n; i++)

        cin >> a[i];

    cout << "Number of Inversion :: " << invcnt(n) << "\n";

    return 0;

}