Insertion Sort Advanced Analysis

c++

#include <bits/stdc++.h>

using namespace std;

/*
 * Complete the 'insertionSort' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts INTEGER_ARRAY arr as parameter.
 */
int fenwick[10000001];
int qry(int n) {
    int res = 0;
    while(n > 0) {
        res += fenwick[n];
        n -= n & -n;
    }
    return res;
}
void update(int n) {
    while(n < 10000001) {
        fenwick[n] += 1;
        n += n & -n;
    }
}
long insertionSort(vector<int>& arr) {
    memset(fenwick, 0, sizeof(fenwick));
    long res = 0, n = arr.size();
    update(arr[0]);
    for(int i = 1; i < n; i++) {
        res += i - qry(arr[i]);
        update(arr[i]);
    }
    return res;
}

int main()
{
    int tc, n;
    cin>>tc;
    while(tc--) {
        cin>>n;
        vector<int> arr(n);
        for(int i = 0; i < n; i++)
            cin>>arr[i];
        cout<<insertionSort(arr)<<endl;
    }
}