Given an array and an integer k, count all inversions in all subarrays of size k.
Example:
Input : a[] = {7, 3, 2, 4, 1},
k = 3;
Output : 6
Explanation: subarrays of size 3 are -
{7, 3, 2}
{3, 2, 4}
{2, 4, 1}
and there inversion count are 3, 1, 2
respectively. So, total number of
inversions are 6.
It is strongly recommended referring Inversion count in an array using BIT
The process of counting inversion is the same as in the above-linked article. First, we calculate the inversion in first k (k is given the size of subarray) elements in the array using BIT. Now after this for every next subarray we subtract the inversion of the first element of the previous subarray and add the inversions of the next element not included in the previous subarray. This process is repeated until the last subarray is processed. On the above example, this algorithm works like this-
a[] = {7, 3, 2, 4, 1},
k = 3;
Inversion are counted for first subarray
A = {7, 3, 2} Let this be equal to invcount_A.
For counting the inversion of subarray B we
subtract the inversion of first element of A,
from invcount_A and add inversions of 4 (last
element of B) in the subarray B.
So, invcount_B = invcount_A - 2 + 0
= 3 - 2 + 0
= 1
Same process is repeated for next subarray
and sum of all inversion count is the answer.
Implementation:
C++
// C++ program to count inversions in all sub arrays// of size k using Binary Indexed Tree#include <bits/stdc++.h>using namespace std;// Returns sum of arr[0..index]. This function assumes// that the array is preprocessed and partial sums of// array elements are stored in BITree[].int getSum(int BITree[], int index){ int sum = 0; // Initialize result // Traverse ancestors of BITree[index] while (index > 0) { // Add current element of BITree to sum sum += BITree[index]; // Move index to parent node in getSum View index -= index & (-index); } return sum;}// Updates a node in Binary Index Tree (BITree) at// given index in BITree. The given value 'val' is // added to BITree[i] and all of its ancestors in // tree.void updateBIT(int BITree[], int n, int index, int val){ // Traverse all ancestors and add 'val' while (index <= n) { // Add 'val' to current node of BI Tree BITree[index] += val; // Update index to that of parent // in update View index += index & (-index); }}// Converts an array to an array with values from 1 to n// and relative order of smaller and greater elements // remains same. For example, {7, -90, 100, 1} is // converted to {3, 1, 4, 2 }void convert(int arr[], int n){ // Create a copy of arrp[] in temp and sort // the temp array in increasing order int temp[n]; for (int i = 0; i < n; i++) temp[i] = arr[i]; sort(temp, temp + n); // Traverse all array elements for (int i = 0; i < n; i++) { // lower_bound() Returns pointer to // the first element greater than // or equal to arr[i] arr[i] = lower_bound(temp, temp + n, arr[i]) - temp + 1; }}// Returns inversion count of all subarray // of size k in arr[0..n-1]int getInvCount(int arr[], int k, int n){ int invcount = 0; // Initialize result // Convert arr[] to an array with values from // 1 to n and relative order of smaller and // greater elements remains same. For example, // {7, -90, 100, 1} is converted to {3, 1, 4, 2 } convert(arr, n); // Create a BIT with size equal to maxElement+1 // (Extra one is used so that elements can be // directly be used as index) int BIT[n + 1]; for (int i = 1; i <= n; i++) BIT[i] = 0; // Get inversion count of first subarray for (int i = k - 1; i >= 0; i--) { // Get count of elements smaller than arr[i] invcount += getSum(BIT, arr[i] - 1); // Add current element to BIT updateBIT(BIT, n, arr[i], 1); } // now calculate the inversion of all other subarrays int ans = invcount; int i = 0, j = k, icnt = 0, jcnt = 0; while (j <= n - 1) { // calculate value of inversion count of first element // in previous subarray icnt = getSum(BIT, arr[i] - 1); updateBIT(BIT, n, arr[i], -1); // calculating inversion count of last element in the // current subarray jcnt = getSum(BIT, n) - getSum(BIT, arr[j]); updateBIT(BIT, n, arr[j], 1); // calculating inversion count of current subarray invcount = invcount - icnt + jcnt; // adding current inversion to the answer ans = ans + invcount; i++, j++; } return ans;}int main(){ int arr[] = { 7, 3, 2, 4, 1 }; int k = 3; int n = sizeof(arr) / sizeof(int); cout << "Number of inversions in all " "subarrays of size " << k <<" are : " << getInvCount(arr, k, n); return 0;} |
Java
// Java program to count inversions in all sub arrays// of size k using Binary Indexed Treeimport java.util.*;class GFG {// Returns sum of arr[0..index]. This function assumes// that the array is preprocessed and partial sums of// array elements are stored in BITree[].static int getSum(int BITree[], int index){ int sum = 0; // Initialize result // Traverse ancestors of BITree[index] while (index > 0) { // Add current element of BITree to sum sum += BITree[index]; // Move index to parent node in getSum View index -= index & (-index); } return sum;}// Updates a node in Binary Index Tree (BITree) at// given index in BITree. The given value 'val' is // added to BITree[i] and all of its ancestors in // tree.static void updateBIT(int BITree[], int n, int index, int val){ // Traverse all ancestors and add 'val' while (index <= n) { // Add 'val' to current node of BI Tree BITree[index] += val; // Update index to that of parent // in update View index += index & (-index); }}// Converts an array to an array with values // from 1 to n and relative order of smaller // and greater elements remains same. // For example, {7, -90, 100, 1} is // converted to {3, 1, 4, 2 }static void convert(int arr[], int n){ // Create a copy of arrp[] in temp and sort // the temp array in increasing order int []temp = new int[n]; for (int i = 0; i < n; i++) temp[i] = arr[i]; Arrays.sort(temp); // Traverse all array elements for (int i = 0; i < n; i++) { // lower_bound() Returns pointer to // the first element greater than // or equal to arr[i] arr[i] = lower_bound(temp, 0, n, arr[i]) + 1; }}static int lower_bound(int[] a, int low, int high, int element){ while(low < high) { int middle = low + (high - low) / 2; if(element > a[middle]) low = middle + 1; else high = middle; } return low;}// Returns inversion count of all subarray // of size k in arr[0..n-1]static int getInvCount(int arr[], int k, int n){ int invcount = 0; // Initialize result // Convert arr[] to an array with values from // 1 to n and relative order of smaller and // greater elements remains same. For example, // {7, -90, 100, 1} is converted to {3, 1, 4, 2 } convert(arr, n); // Create a BIT with size equal to maxElement+1 // (Extra one is used so that elements can be // directly be used as index) int []BIT = new int[n + 1]; for (int i = 1; i <= n; i++) BIT[i] = 0; // Get inversion count of first subarray for (int i = k - 1; i >= 0; i--) { // Get count of elements smaller than arr[i] invcount += getSum(BIT, arr[i] - 1); // Add current element to BIT updateBIT(BIT, n, arr[i], 1); } // now calculate the inversion of // all other subarrays int ans = invcount; int i = 0, j = k, icnt = 0, jcnt = 0; while (j <= n - 1) { // calculate value of inversion count of // first element in previous subarray icnt = getSum(BIT, arr[i] - 1); updateBIT(BIT, n, arr[i], -1); // calculating inversion count of // last element in the current subarray jcnt = getSum(BIT, n) - getSum(BIT, arr[j]); updateBIT(BIT, n, arr[j], 1); // calculating inversion count // of current subarray invcount = invcount - icnt + jcnt; // adding current inversion to the answer ans = ans + invcount; i++; j++; } return ans;}// Driver Codepublic static void main(String[] args){ int arr[] = { 7, 3, 2, 4, 1 }; int k = 3; int n = arr.length; System.out.println("Number of inversions in all " + "subarrays of size " + k + " are : " + getInvCount(arr, k, n)); }} // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to count inversions in all sub arrays# of size k using Binary Indexed Treefrom bisect import bisect_left as lower_bound# Returns sum of arr[0..index]. This function assumes# that the array is preprocessed and partial sums of# array elements are stored in BITree.def getSum(BITree, index): sum = 0 # Initialize result # Traverse ancestors of BITree[index] while (index > 0): # Add current element of BITree to sum sum += BITree[index] # Move index to parent node in getSum View index -= index & (-index) return sum# Updates a node in Binary Index Tree (BITree) at# given index in BITree. The given value 'val' is# added to BITree[i] and all of its ancestors in# tree.def updateBIT(BITree, n, index, val): # Traverse all ancestors and add 'val' while (index <= n): # Add 'val' to current node of BI Tree BITree[index] += val # Update index to that of parent # in update View index += index & (-index)# Converts an array to an array with values from 1 to n# and relative order of smaller and greater elements# remains same. For example,7, -90, 100, 1 is# converted to3, 1, 4, 2def convert(arr, n): # Create a copy of arrp in temp and sort # the temp array in increasing order temp = [0]*(n) for i in range(n): temp[i] = arr[i] temp = sorted(temp) # Traverse all array elements for i in range(n): # lower_bound() Returns pointer to # the first element greater than # or equal to arr[i] arr[i] = lower_bound(temp, arr[i]) + 1# Returns inversion count of all subarray# of size k in arr[0..n-1]def getInvCount(arr, k, n): invcount = 0 # Initialize result # Convert arr to an array with values from # 1 to n and relative order of smaller and # greater elements remains same. For example, # 7, -90, 100, 1 is converted to3, 1, 4, 2 convert(arr, n) # Create a BIT with size equal to maxElement+1 # (Extra one is used so that elements can be # directly be used as index) BIT=[0]*(n + 1) for i in range(1, n + 1): BIT[i] = 0 # Get inversion count of first subarray for i in range(k - 1, -1, -1): # Get count of elements smaller than arr[i] invcount += getSum(BIT, arr[i] - 1) # Add current element to BIT updateBIT(BIT, n, arr[i], 1) # now calculate the inversion of all other subarrays ans = invcount i = 0 j = k icnt = 0 jcnt = 0 while (j <= n - 1): # calculate value of inversion count of first element # in previous subarray icnt = getSum(BIT, arr[i] - 1) updateBIT(BIT, n, arr[i], -1) # calculating inversion count of last element in the # current subarray jcnt = getSum(BIT, n) - getSum(BIT, arr[j]) updateBIT(BIT, n, arr[j], 1) # calculating inversion count of current subarray invcount = invcount - icnt + jcnt # adding current inversion to the answer ans = ans + invcount i += 1 j += 1 return ans# Driver codeif __name__ == '__main__': arr= [7, 3, 2, 4, 1] k = 3 n = len(arr) print("Number of inversions in all subarrays of size " ,k," are : ",getInvCount(arr, k, n))# This code is contributed by mohit kumar 29 |
C#
// C# program to count inversions in all sub arrays// of size k using Binary Indexed Treeusing System;class GFG{ // Returns sum of arr[0..index]. This function assumes// that the array is preprocessed and partial sums of// array elements are stored in BITree[].static int getSum(int []BITree, int index){ int sum = 0; // Initialize result // Traverse ancestors of BITree[index] while (index > 0) { // Add current element of BITree to sum sum += BITree[index]; // Move index to parent node in getSum View index -= index & (-index); } return sum;}// Updates a node in Binary Index Tree (BITree) at// given index in BITree. The given value 'val' is // added to BITree[i] and all of its ancestors in // tree.static void updateBIT(int []BITree, int n, int index, int val){ // Traverse all ancestors and add 'val' while (index <= n) { // Add 'val' to current node of BI Tree BITree[index] += val; // Update index to that of parent // in update View index += index & (-index); }}// Converts an array to an array with values // from 1 to n and relative order of smaller // and greater elements remains same. // For example, {7, -90, 100, 1} is // converted to {3, 1, 4, 2 }static void convert(int []arr, int n){ // Create a copy of arrp[] in temp and sort // the temp array in increasing order int []temp = new int[n]; for (int i = 0; i < n; i++) temp[i] = arr[i]; Array.Sort(temp); // Traverse all array elements for (int i = 0; i < n; i++) { // lower_bound() Returns pointer to // the first element greater than // or equal to arr[i] arr[i] = lower_bound(temp, 0, n, arr[i]) + 1; }}static int lower_bound(int[] a, int low, int high, int element){ while(low < high) { int middle = low + (high - low) / 2; if(element > a[middle]) low = middle + 1; else high = middle; } return low;}// Returns inversion count of all subarray // of size k in arr[0..n-1]static int getInvCount(int []arr, int k, int n){ int invcount = 0; // Initialize result // Convert arr[] to an array with values from // 1 to n and relative order of smaller and // greater elements remains same. For example, // {7, -90, 100, 1} is converted to {3, 1, 4, 2 } convert(arr, n); // Create a BIT with size equal to maxElement+1 // (Extra one is used so that elements can be // directly be used as index) int []BIT = new int[n + 1]; for (int i = 1; i <= n; i++) BIT[i] = 0; // Get inversion count of first subarray for (int i = k - 1; i >= 0; i--) { // Get count of elements smaller than arr[i] invcount += getSum(BIT, arr[i] - 1); // Add current element to BIT updateBIT(BIT, n, arr[i], 1); } // now calculate the inversion of // all other subarrays int ans = invcount; int x = 0, j = k, icnt = 0, jcnt = 0; while (j <= n - 1) { // calculate value of inversion count of // first element in previous subarray icnt = getSum(BIT, arr[x] - 1); updateBIT(BIT, n, arr[x], -1); // calculating inversion count of // last element in the current subarray jcnt = getSum(BIT, n) - getSum(BIT, arr[j]); updateBIT(BIT, n, arr[j], 1); // calculating inversion count // of current subarray invcount = invcount - icnt + jcnt; // adding current inversion to the answer ans = ans + invcount; x++; j++; } return ans;}// Driver Codestatic public void Main (){ int []arr = { 7, 3, 2, 4, 1 }; int k = 3; int n = arr.Length; Console.Write("Number of inversions in all " + "subarrays of size " + k + " are : " + getInvCount(arr, k, n));}} // This code is contributed by ajit. |
Javascript
<script> // Javascript program to count inversions in all sub arrays // of size k using Binary Indexed Tree // Returns sum of arr[0..index]. This function assumes // that the array is preprocessed and partial sums of // array elements are stored in BITree[]. function getSum(BITree, index) { let sum = 0; // Initialize result // Traverse ancestors of BITree[index] while (index > 0) { // Add current element of BITree to sum sum += BITree[index]; // Move index to parent node in getSum View index -= index & (-index); } return sum; } // Updates a node in Binary Index Tree (BITree) at // given index in BITree. The given value 'val' is // added to BITree[i] and all of its ancestors in // tree. function updateBIT(BITree, n, index, val) { // Traverse all ancestors and add 'val' while (index <= n) { // Add 'val' to current node of BI Tree BITree[index] += val; // Update index to that of parent // in update View index += index & (-index); } } // Converts an array to an array with values // from 1 to n and relative order of smaller // and greater elements remains same. // For example, {7, -90, 100, 1} is // converted to {3, 1, 4, 2 } function convert(arr, n) { // Create a copy of arrp[] in temp and sort // the temp array in increasing order let temp = new Array(n); for (let i = 0; i < n; i++) temp[i] = arr[i]; temp.sort(function(a, b){return a - b}); // Traverse all array elements for (let i = 0; i < n; i++) { // lower_bound() Returns pointer to // the first element greater than // or equal to arr[i] arr[i] = lower_bound(temp, 0, n, arr[i]) + 1; } } function lower_bound(a, low, high, element) { while(low < high) { let middle = low + parseInt((high - low) / 2, 10); if(element > a[middle]) low = middle + 1; else high = middle; } return low; } // Returns inversion count of all subarray // of size k in arr[0..n-1] function getInvCount(arr, k, n) { let invcount = 0; // Initialize result // Convert arr[] to an array with values from // 1 to n and relative order of smaller and // greater elements remains same. For example, // {7, -90, 100, 1} is converted to {3, 1, 4, 2 } convert(arr, n); // Create a BIT with size equal to maxElement+1 // (Extra one is used so that elements can be // directly be used as index) let BIT = new Array(n + 1); for (let i = 1; i <= n; i++) BIT[i] = 0; // Get inversion count of first subarray for (let i = k - 1; i >= 0; i--) { // Get count of elements smaller than arr[i] invcount += getSum(BIT, arr[i] - 1); // Add current element to BIT updateBIT(BIT, n, arr[i], 1); } // now calculate the inversion of // all other subarrays let ans = invcount; let x = 0, j = k, icnt = 0, jcnt = 0; while (j <= n - 1) { // calculate value of inversion count of // first element in previous subarray icnt = getSum(BIT, arr[x] - 1); updateBIT(BIT, n, arr[x], -1); // calculating inversion count of // last element in the current subarray jcnt = getSum(BIT, n) - getSum(BIT, arr[j]); updateBIT(BIT, n, arr[j], 1); // calculating inversion count // of current subarray invcount = invcount - icnt + jcnt; // adding current inversion to the answer ans = ans + invcount; x++; j++; } return ans; } let arr = [ 7, 3, 2, 4, 1 ]; let k = 3; let n = arr.length; document.write("Number of inversions in all " + "subarrays of size " + k + " are : " + getInvCount(arr, k, n)); </script> |
Output
Number of inversions in all subarrays of size 3 are : 6
Time Complexity :- inversion count of first subarray takes O(k log(n)) time and for all other subarray it takes O((n-k)log(n)). So overall time complexity is : O(n log n).
Auxiliary space:- O(n)
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
