Array range queries to find the maximum Fibonacci number with updates | Java code for range maximum query and updates ; A utility function to get the middle index of given range . ; Function to create hash table to check Fibonacci numbers ; * A recursive function to get the sum of * values in given range of the array . * The following are parameters for this function . * * st -> Pointer to segment tree * node -> Index of current node * in the segment tree . * ss & se -> Starting and ending indexes * of the segment represented * by current node , i . e . , st [ node ] * l & r -> Starting and ending indexes * of range query ; If segment of this node is completely part of given range , then return the max of segment ; If segment of this node does not belong to given range ; If segment of this node is partially the part of given range ; * A recursive function to update the nodes which * have the given index in their range . The following * are parameters st , ss and se are same as defined * above index -> index of the element to be updated . ; update value in array and in segment tree ; Return max of elements in range from index l ( query start ) to r ( query end ) . ; Check for erroneous input values ; A recursive function that constructs Segment Tree for array [ ss . . se ] . si is index of current node in segment tree st ; If there is one element in array , store it in current node of segment tree and return ; If there are more than one elements , then recur for left and right subtrees and store the max of values in this node ; * Function to construct segment tree * from given array . This function allocates * memory for segment tree . ; Height of segment tree ; Maximum size of segment tree ; Allocate memory ; Fill the allocated memory st ; Return the constructed segment tree ; Driver code ; find the largest node value in the array ; creating a set containing all fibonacci numbers upto the maximum data value in the array ; Build segment tree from given array ; Print max of values in array from index 1 to 3 ; Update : set arr [ 1 ] = 8 and update corresponding segment tree nodes . ; Find max after the value is updated
import java . util . Arrays ; import java . util . HashSet ; import java . util . Set ; class GFG { static Set < Integer > fibonacci = new HashSet < > ( ) ; static int getMid ( int s , int e ) { return s + ( e - s ) / 2 ; } static void createHash ( int maxElement ) { int prev = 0 , curr = 1 ; fibonacci . add ( prev ) ; fibonacci . add ( curr ) ; while ( curr <= maxElement ) { int temp = curr + prev ; fibonacci . add ( temp ) ; prev = curr ; curr = temp ; } } static int MaxUtil ( int [ ] st , int ss , int se , int l , int r , int node ) { if ( l <= ss && r >= se ) return st [ node ] ; if ( se < l ss > r ) return - 1 ; int mid = getMid ( ss , se ) ; return Math . max ( MaxUtil ( st , ss , mid , l , r , 2 * node + 1 ) , MaxUtil ( st , mid + 1 , se , l , r , 2 * node + 2 ) ) ; } static void updateValue ( int arr [ ] , int [ ] st , int ss , int se , int index , int value , int node ) { if ( index < ss index > se ) { System . out . println ( " Invalid ▁ Input " ) ; return ; } if ( ss == se ) { arr [ index ] = value ; if ( fibonacci . contains ( value ) ) st [ node ] = value ; else st [ node ] = - 1 ; } else { int mid = getMid ( ss , se ) ; if ( index >= ss && index <= mid ) updateValue ( arr , st , ss , mid , index , value , 2 * node + 1 ) ; else updateValue ( arr , st , mid + 1 , se , index , value , 2 * node + 2 ) ; st [ node ] = Math . max ( st [ 2 * node + 1 ] , st [ 2 * node + 2 ] ) ; } return ; } static int getMax ( int [ ] st , int n , int l , int r ) { if ( l < 0 r > n - 1 l > r ) { System . out . printf ( "Invalid InputNEW_LINE"); return - 1 ; } return MaxUtil ( st , 0 , n - 1 , l , r , 0 ) ; } static int constructSTUtil ( int arr [ ] , int ss , int se , int [ ] st , int si ) { if ( ss == se ) { if ( fibonacci . contains ( arr [ ss ] ) ) st [ si ] = arr [ ss ] ; else st [ si ] = - 1 ; return st [ si ] ; } int mid = getMid ( ss , se ) ; st [ si ] = Math . max ( constructSTUtil ( arr , ss , mid , st , si * 2 + 1 ) , constructSTUtil ( arr , mid + 1 , se , st , si * 2 + 2 ) ) ; return st [ si ] ; } static int [ ] constructST ( int arr [ ] , int n ) { int x = ( int ) ( Math . ceil ( Math . log ( n ) / Math . log ( 2 ) ) ) ; int max_size = 2 * ( int ) Math . pow ( 2 , x ) - 1 ; int [ ] st = new int [ max_size ] ; constructSTUtil ( arr , 0 , n - 1 , st , 0 ) ; return st ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 3 , 5 , 7 , 9 , 11 } ; int n = arr . length ; int maxEle = Arrays . stream ( arr ) . max ( ) . getAsInt ( ) ; createHash ( maxEle ) ; int [ ] st = constructST ( arr , n ) ; System . out . println ( " Maximum ▁ fibonacci ▁ number ▁ in ▁ given ▁ range ▁ = ▁ " + getMax ( st , n , 1 , 3 ) ) ; updateValue ( arr , st , 0 , n - 1 , 3 , 8 , 0 ) ; System . out . println ( " Updated ▁ Maximum ▁ fibonacci ▁ number ▁ in ▁ given ▁ range ▁ = ▁ " + getMax ( st , n , 1 , 3 ) ) ; } }