Introduction
This blog will discuss the problem "Count of Inversions of size K in a given array". In this problem, we will be given an array containing ‘N’ distinct integers and a positive integer ‘K’. We have to find the count of inversions of size K in the given array. Before proceeding further, let’s understand what do we mean by an inversion of size K in an array.
Let’s say we have an array ‘arr’ having N integers. An inversion of size K (K <= N) in the array will be a subsequence “arr[ i_{1 }], arr[ i_{2} ], ……, arr[ i_{K} ]” such that:
arr[ i_{1 }] > arr[ i_{2} ] > ……> arr[ i_{K} ] and
0 <= i_{1} < i_{2} <.......< i_{K}
Let's take an example to understand the problem:
Suppose we have the following given information 
arr = { 8, 7, 1, 6, 2}
N = 5
K = 3
We have to find the count of inversions of length 3 (K = 3) in the given array.
Inversions of length 3 in the given array are:
{8, 7, 1}
{8, 7, 6}
{8, 7, 2}
{8, 6, 2}
{7, 6, 2}
Here, we can see that there is a total of five inversions of length three in the given array.
Now that we understand the problem, let's discuss the approach to solve it in the next section.
Also read, Euclid GCD Algorithm
Solution Approach
This section will discuss an approach to solve the problem of finding the count of inversions of size K in a given array using a Binary Indexed Tree, also called a Fenwick Tree. For creating a binary indexed tree, first convert the given array to a permutation of integers from 1 to N, maintaining the relative order of values of the array elements.
For example array { 8, 7, 1, 6, 2} will be converted to {5, 4, 1, 3, 2}
Now, the approach is to create a twodimensional array "bit[][]" to create 'K' Fenwick trees. Here bit[i][j] stores the number of inversions of length 'i', which start with 'j.'
Fill the array' bit[i][j]' starting from the last element of the array. Finally, the total number of inversions of length K will be the sum of bit[K][i], where 1 <= i <=N, as bit[K][i] denotes the number of inversions of size K which starts from 'i'.
Algorithm 
Step 1. First, write the main function. Inside the main function, call the function "convertToPermutation()" function to convert the given array to a permutation of numbers from 1 to N, maintaining the relative order of values of the array elements. Next, call the function "findInversionsCount()" to find the count of inversions of size K in the given array.
Step 2. Create the function "convertToPermutation()" to convert the given array to a permutation of numbers from 1 to N, maintaining the relative order of values of the array elements. Inside the function, first, create a copy 'temp' of the given array 'arr' and then traverse array 'arr .'For each element in 'arr,' find the number of elements less than or equal to it and then update its value.
Step 3. Globally define bit[K][N] to store K binary indexed trees, where bit[i][j] denotes the number of inversions of length 'i' starting with 'j .'Create the function "findInversionsCount()" to find the count of inversions of size K in the given array. Inside the function, start iterating 'arr' from its last element to the first element. For each element ‘arr[i]’, first, update binary indexed tree for length = 1. Then run a loop and update each binary indexed tree. Finally, return sum of bit[K][i], where 1<=i<=N.
Step 4. Create function "update()" to update a binary indexed tree and "findSum()" to find the sum of inversions of a given length using the binary indexed tree.
C++ code:


Algorithm Complexity:
Time Complexity: O(N * K * log(N))
In the function "findInversionsCount()" to find the count of inversions of size K in a given array, we have created a for loop to iterate through each element of the array, and for each element of the array, we have maintained K binary indexed tree, for which we have called "update()" and "findSum()" functions which take O(log N) time. So, the overall time complexity is O(N * K * log(N)), where 'N' is the number of elements in a given array.
Space Complexity: O(N * K)
In the above program to find the count of inversions of size K in a given array, we have created a bit[N][K] array to store K binary indexed tree, each having N nodes. So, the space complexity is O(N * K).