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
function getSum ( BITree , index ) { let ans = 0 ; index += 1 ; while ( index > 0 ) { ans += BITree [ index ] ; index -= index & ( - index ) ; } return ans ; } function updateBIT ( BITree , n , index , val ) { index = index + 1 ; while ( index <= n ) { BITree [ index ] += val ; index += index & ( - index ) ; } } function constructBITree ( arr , n ) { let BITree = new Array ( n + 1 ) ; for ( let i = 0 ; i <= n ; i ++ ) BITree [ i ] = 0 ; for ( let i = 0 ; i < n ; i ++ ) updateBIT ( BITree , n , i , arr [ i ] ) ; return BITree ; } function getLowerBound ( BITree , arr , n , k ) { let lb = - 1 ; let l = 0 , r = n - 1 ; while ( l <= r ) { let mid = Math . floor ( l + ( r - l ) / 2 ) ; if ( getSum ( BITree , mid ) >= k ) { r = mid - 1 ; lb = mid ; } else l = mid + 1 ; } return lb ; } function performQueries ( A , n , q ) { let BITree = constructBITree ( A , n ) ; for ( let i = 0 ; i < q . length ; i ++ ) { let id = q [ i ] [ 0 ] ; if ( id == 1 ) { let idx = q [ i ] [ 1 ] ; let val = q [ i ] [ 2 ] ; A [ idx ] += val ; updateBIT ( BITree , n , idx , val ) ; } else { let k = q [ i ] [ 1 ] ; let lb = getLowerBound ( BITree , A , n , k ) ; document . write ( lb + " " ) ; } } } let A = [ 1 , 2 , 3 , 5 , 8 ] ; let n = A . length ; let q = [ [ 1 , 0 , 2 ] , [ 2 , 5 , 0 ] , [ 1 , 3 , 5 ] ] ; performQueries ( A , n , q ) ;