Queries to find the Lower Bound of K from Prefix Sum Array with updates using Fenwick Tree | Function to calculate and return the sum of arr [ 0. . index ] ; Traverse ancestors of BITree [ index ] ; Update the sum of current element of BIT to ans ; Update index to that of the parent node in getSum ( ) view by subtracting LSB ( Least Significant Bit ) ; Function to update the Binary Index Tree by replacing all ancestors of index by their respective sum with val ; Traverse all ancestors and sum with ' val ' . ; Add ' val ' to current node of BIT ; Update index to that of the parent node in updateBit ( ) view by adding LSB ( Least Significant Bit ) ; Function to construct the Binary Indexed Tree for the given array ; Initialize the Binary Indexed Tree ; Store the actual values in BITree [ ] using update ( ) ; Function to obtain and return the index of lower_bound of k ; Store the Binary Indexed Tree ; Solve each query in Q ; Update the values of all ancestors of idx ; Driver Code
def getSum ( BITree , index ) : NEW_LINE INDENT ans = 0 NEW_LINE index += 1 NEW_LINE while ( index > 0 ) : NEW_LINE INDENT ans += BITree [ index ] NEW_LINE index -= index & ( - index ) NEW_LINE DEDENT return ans NEW_LINE DEDENT def updateBIT ( BITree , n , index , val ) : NEW_LINE INDENT index = index + 1 NEW_LINE while ( index <= n ) : NEW_LINE INDENT BITree [ index ] += val NEW_LINE index += index & ( - index ) NEW_LINE DEDENT DEDENT def constructBITree ( arr , n ) : NEW_LINE INDENT BITree = [ 0 ] * ( n + 1 ) NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT BITree [ i ] = 0 NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT updateBIT ( BITree , n , i , arr [ i ] ) NEW_LINE DEDENT return BITree NEW_LINE DEDENT def getLowerBound ( BITree , arr , n , k ) : NEW_LINE INDENT lb = - 1 NEW_LINE l = 0 NEW_LINE r = n - 1 NEW_LINE while ( l <= r ) : NEW_LINE INDENT mid = l + ( r - l ) // 2 NEW_LINE if ( getSum ( BITree , mid ) >= k ) : NEW_LINE INDENT r = mid - 1 NEW_LINE lb = mid NEW_LINE DEDENT else : NEW_LINE INDENT l = mid + 1 NEW_LINE DEDENT DEDENT return lb NEW_LINE DEDENT def performQueries ( A , n , q ) : NEW_LINE INDENT BITree = constructBITree ( A , n ) NEW_LINE for i in range ( len ( q ) ) : NEW_LINE INDENT id = q [ i ] [ 0 ] NEW_LINE if ( id == 1 ) : NEW_LINE INDENT idx = q [ i ] [ 1 ] NEW_LINE val = q [ i ] [ 2 ] NEW_LINE A [ idx ] += val NEW_LINE updateBIT ( BITree , n , idx , val ) NEW_LINE DEDENT else : NEW_LINE INDENT k = q [ i ] [ 1 ] NEW_LINE lb = getLowerBound ( BITree , A , n , k ) NEW_LINE print ( lb ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = [ 1 , 2 , 3 , 5 , 8 ] NEW_LINE n = len ( A ) NEW_LINE q = [ [ 1 , 0 , 2 ] , [ 2 , 5 , 0 ] , [ 1 , 3 , 5 ] ] NEW_LINE performQueries ( A , n , q ) NEW_LINE DEDENT