Count smaller elements on right side and greater elements on left side using Binary Index Tree | Python3 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 ; lower_bound ( ) Returns pointer 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
from bisect import bisect_left as lower_bound NEW_LINE def getSum ( BITree , index ) : NEW_LINE INDENT s = 0 NEW_LINE while index > 0 : NEW_LINE INDENT s += BITree [ index ] NEW_LINE index -= index & ( - index ) NEW_LINE DEDENT return s NEW_LINE DEDENT def updateBIT ( BITree , n , index , val ) : NEW_LINE ' NEW_LINE INDENT while index <= n : NEW_LINE INDENT BITree [ index ] += val NEW_LINE index += index & ( - index ) NEW_LINE DEDENT DEDENT def convert ( arr , n ) : NEW_LINE INDENT temp = [ 0 ] * n NEW_LINE for i in range ( n ) : NEW_LINE INDENT temp [ i ] = arr [ i ] NEW_LINE DEDENT temp . sort ( ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT arr [ i ] = lower_bound ( temp , arr [ i ] ) + 1 NEW_LINE DEDENT DEDENT def findElements ( arr , n ) : NEW_LINE INDENT convert ( arr , n ) NEW_LINE BIT = [ 0 ] * ( n + 1 ) NEW_LINE smaller_right = [ 0 ] * n NEW_LINE greater_left = [ 0 ] * n NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT smaller_right [ i ] = getSum ( BIT , arr [ i ] - 1 ) NEW_LINE updateBIT ( BIT , n , arr [ i ] , 1 ) NEW_LINE DEDENT print ( " Smaller ▁ right : " , end = " ▁ " ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT print ( smaller_right [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT BIT [ i ] = 0 NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT greater_left [ i ] = i - getSum ( BIT , arr [ i ] ) NEW_LINE updateBIT ( BIT , n , arr [ i ] , 1 ) NEW_LINE DEDENT print ( " Greater ▁ left : " , end = " ▁ " ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT print ( greater_left [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 12 , 1 , 2 , 3 , 0 , 11 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE findElements ( arr , n ) NEW_LINE DEDENT