Count inversions in an array | Set 3 ( Using BIT ) | Returns sum of arr [ 0. . index ] . This function assumes that the array is preprocessed and partial sums of array elements are stored in BITree [ ] . ; Initialize result ; Traverse ancestors of BITree [ index ] ; Add current element of BITree to sum ; Move index to parent node in getSum View ; 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 . ; Traverse all ancestors and add ' val ' ; Add ' val ' to current node of BI Tree ; Update index to that of parent in update View ; 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 } ; Create a copy of arrp [ ] in temp and sort the temp array in increasing order ; Traverse all array elements ; lower_bound ( ) Returns pointer to the first element greater than or equal to arr [ i ] ; Returns inversion count arr [ 0. . n - 1 ] ; 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 } ; Create a BIT with size equal to maxElement + 1 ( Extra one is used so that elements can be directly be used as index ) ; Traverse all elements from right . ; Get count of elements smaller than arr [ i ] ; Add current element to BIT ; Driver code
function getSum ( BITree , index ) { let sum = 0 ; while ( index > 0 ) { sum += BITree [ index ] ; index -= index & ( - index ) ; } return sum ; } function updateBIT ( BITree , n , index , val ) { while ( index <= n ) { BITree [ index ] += val ; index += index & ( - index ) ; } } function convert ( arr , n ) { let temp = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) temp [ i ] = arr [ i ] ; temp . sort ( function ( a , b ) { return a - b ; } ) ; for ( let i = 0 ; i < n ; i ++ ) { arr [ i ] = lower_bound ( temp , 0 , n , arr [ i ] ) + 1 ; } } function lower_bound ( a , low , high , element ) { while ( low < high ) { let middle = low + Math . floor ( ( high - low ) / 2 ) ; if ( element > a [ middle ] ) low = middle + 1 ; else high = middle ; } return low ; } function getInvCount ( arr , n ) { let invcount = 0 ; convert ( arr , n ) ; let BIT = new Array ( n + 1 ) ; for ( let i = 1 ; i <= n ; i ++ ) BIT [ i ] = 0 ; for ( let i = n - 1 ; i >= 0 ; i -- ) { invcount += getSum ( BIT , arr [ i ] - 1 ) ; updateBIT ( BIT , n , arr [ i ] , 1 ) ; } return invcount ; } let arr = [ 8 , 4 , 2 , 1 ] ; let n = arr . length ; document . write ( " " + getInvCount ( arr , n ) ) ;