Count smaller elements on right side and greater elements on left side using Binary Index Tree | Java implementation of the approach ; Function to return the 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 ; Arrays . binarySearch ( ) returns index to the first element greater than or equal to arr [ i ] ; Function to find smaller_right array ; 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 ) ; To store smaller elements in right side and greater elements on left side ; Traverse all elements from right . ; Get count of elements smaller than arr [ i ] ; Add current element to BIT ; Print smaller_right array ; Find all left side greater elements ; Get count of elements greater than arr [ i ] ; Add current element to BIT ; Print greater_left array ; Driver code ; Function call
import java . io . * ; import java . util . * ; class GFG { public static int getSum ( int BITree [ ] , int index ) { int sum = 0 ; while ( index > 0 ) { sum += BITree [ index ] ; index -= index & ( - index ) ; } return sum ; } public static void updateBIT ( int BITree [ ] , int n , int index , int val ) { while ( index <= n ) { BITree [ index ] += val ; index += index & ( - index ) ; } } public static void convert ( int arr [ ] , int n ) { int [ ] temp = new int [ n ] ; for ( int i = 0 ; i < n ; i ++ ) temp [ i ] = arr [ i ] ; Arrays . sort ( temp ) ; for ( int i = 0 ; i < n ; i ++ ) { arr [ i ] = Arrays . binarySearch ( temp , arr [ i ] ) + 1 ; } } public static void findElements ( int arr [ ] , int n ) { convert ( arr , n ) ; int [ ] BIT = new int [ n + 1 ] ; for ( int i = 1 ; i <= n ; i ++ ) BIT [ i ] = 0 ; int [ ] smaller_right = new int [ n ] ; int [ ] greater_left = new int [ n ] ; for ( int i = n - 1 ; i >= 0 ; i -- ) { smaller_right [ i ] = getSum ( BIT , arr [ i ] - 1 ) ; updateBIT ( BIT , n , arr [ i ] , 1 ) ; } System . out . print ( " Smaller ▁ right : ▁ " ) ; for ( int i = 0 ; i < n ; i ++ ) System . out . print ( smaller_right [ i ] + " ▁ " ) ; System . out . println ( ) ; for ( int i = 1 ; i <= n ; i ++ ) BIT [ i ] = 0 ; for ( int i = 0 ; i < n ; i ++ ) { greater_left [ i ] = i - getSum ( BIT , arr [ i ] ) ; updateBIT ( BIT , n , arr [ i ] , 1 ) ; } System . out . print ( " Greater ▁ left : ▁ " ) ; for ( int i = 0 ; i < n ; i ++ ) System . out . print ( greater_left [ i ] + " ▁ " ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 12 , 1 , 2 , 3 , 0 , 11 , 4 } ; int n = arr . length ; findElements ( arr , n ) ; } }