How can I find the sum of all possible inversion count in all the subarray?

Question

I need to find some of the inversion counts in all subarray in the least possible time complexity.
Two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

I have tried it using Fenwick Tree implementation but getting time limit exceeded.

I want a code that is an optimized version of this:

import java.util.*; 

public class Main { 
static BIT bit; 

static long inversionCountBIT1(int[] arr, int start, 
                                        int end) 
{ 
    bit = new BIT(arr.length); 
    long count = 0; 
    for (int index = start; index >= end; index--) { 
        count += bit.read(arr[index]); 
        bit.update(arr[index], 1); 
    } 
    return count; 
} 

static long inversionCountBIT2(int[] arr, int start, 
                                int end, long val) 
{ 
    bit.update(arr[start + 1], -1);
    int numGreaterThanFirst = start - end - bit.read(arr[start + 1] + 1); 
    long count = val + bit.read(arr[end]) - numGreaterThanFirst; 
    bit.update(arr[end], 1); 

    return count; 
} 

public static long inversionCount(int n, int k, int[] arr) 
{ 
    bit = new BIT(n); 
    HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>(); 
    int[] asort = arr.clone(); 

    Arrays.sort(asort); 
    int index = 0; 
    int current = 1; 
    for (int i = 0; i < n; i++) { 
        if (!freq.containsKey(asort[i])) { 
            freq.put(asort[i], current); 
            current++; 
        } 
    } 
    for (int i = 0; i < n; i++) { 
        arr[i] = freq.get(arr[i]); 
    } 

    long count = 0; 
    long val = 0; 

    for (int start = n - 1; start >= k - 1; start--) { 
        int end = start - k + 1; 
        if (start == n - 1) { 
            val = inversionCountBIT1(arr, n - 1, n - k); 
        } else { 
            val = inversionCountBIT2(arr, start, end, val); 
        } 
        count += val; 
    } 
    return count; 
} 

public static void main(String[] args) throws Exception 
{   
    Scanner scn  = new Scanner(System.in);
    int t=scn.nextInt() ; 
    int n;
    long k ; 
    while(t>0)
    {  
        n= scn.nextInt()  ; 
        k =scn.nextLong() ; 
        long result = 0; 
    int[] arr =new int[n]; 
    for(int i=0;i<n;i++)
    {
        arr[i]=scn.nextInt() ;
    }
    for(int i=1;i<=n;i++)
    result += inversionCount(n, i, arr); 
    System.out.println(result%k); 
    t--;
} 
}

static class BIT { 
    int[] tree; 
    int maxVal; 
public BIT(int N) 
    { 
        tree = new int[N + 1]; 
        maxVal = N; 
    } 

    void update(int index, int val) 
    { 
        while (index <= maxVal) { 
            tree[index] += val; 
            index += (index & -index); 
        } 
    } 

    int read(int index) 
    { 
        --index; 
        int cumulative_sum = 0; 
        while (index > 0) { 
            cumulative_sum += tree[index]; 
            index -= (index & -index); 
        } 
        return cumulative_sum; 
    } 
}; 
} 

Time Limit Exceeded

Answer 1

First of all sort the array in decreasing order and then traverse the tree and using BIT keep the sum of all the index position which have value greater then the value at current index then multiply that sum and (n-current index).

int main()
{
    memset(bit,0,sizeof(bit));

    long long n;
    sfl(n)

    util arr[n+1];

    f(i,1,n+1)
    {
        sfl(arr[i].val)
        arr[i].idx=i;
    }

    sort(arr+1,arr+n+1,cmp);

    ll ans=0;

    f(i,1,n+1)
    {
        ll temp1=totsum(arr[i].idx);
        ans=(ans+(temp1*(n-arr[i].idx+1))%mod)%mod;
        update(arr[i].idx,arr[i].idx,n);
    }

    pfl(ans)
}