Queries to find the Lower Bound of K from Prefix Sum Array with updates using Fenwick Tree | C # program to implement the above approach ; 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
using System ; class GFG { static int getSum ( int [ ] BITree , int index ) { int ans = 0 ; index += 1 ; while ( index > 0 ) { ans += BITree [ index ] ; index -= index & ( - index ) ; } return ans ; } static void updateBIT ( int [ ] BITree , int n , int index , int val ) { index = index + 1 ; while ( index <= n ) { BITree [ index ] += val ; index += index & ( - index ) ; } } static int [ ] constructBITree ( int [ ] arr , int n ) { int [ ] BITree = new int [ n + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) BITree [ i ] = 0 ; for ( int i = 0 ; i < n ; i ++ ) updateBIT ( BITree , n , i , arr [ i ] ) ; return BITree ; } static int getLowerBound ( int [ ] BITree , int [ ] arr , int n , int k ) { int lb = - 1 ; int l = 0 , r = n - 1 ; while ( l <= r ) { int mid = l + ( r - l ) / 2 ; if ( getSum ( BITree , mid ) >= k ) { r = mid - 1 ; lb = mid ; } else l = mid + 1 ; } return lb ; } static void performQueries ( int [ ] A , int n , int [ , ] q ) { int [ ] BITree = constructBITree ( A , n ) ; for ( int i = 0 ; i < q . GetLength ( 0 ) ; i ++ ) { int id = q [ i , 0 ] ; if ( id == 1 ) { int idx = q [ i , 1 ] ; int val = q [ i , 2 ] ; A [ idx ] += val ; updateBIT ( BITree , n , idx , val ) ; } else { int k = q [ i , 1 ] ; int lb = getLowerBound ( BITree , A , n , k ) ; Console . WriteLine ( lb ) ; } } } public static void Main ( String [ ] args ) { int [ ] A = { 1 , 2 , 3 , 5 , 8 } ; int n = A . Length ; int [ , ] q = { { 1 , 0 , 2 } , { 2 , 5 , 0 } , { 1 , 3 , 5 } } ; performQueries ( A , n , q ) ; } }