text: Queries to evaluate the given equation in a range [ L , R ] | Java Program to implement the above approach ; Function to obtain the middle index of the range ; Recursive function to get the sum of values in the given range from 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 the segment of this node lies completely within the given range ; Return maximum in the segment ; If the segment of this node lies outside the given range ; If segment of this node lies partially in the given range ; Function to return the maximum in the range from [ l , r ] ; Check for erroneous input values ; Function to conSegment Tree for the subarray [ ss . . se ] ; For a single element ; Otherwise ; Recur for left subtree ; Recur for right subtree ; Function to conSegment Tree from the given array ; Height of Segment Tree ; Maximum size of Segment Tree ; Allocate memory ; Fill the allocated memory ; Return the constructed Segment Tree ; Driver Code ; Build the Segment Tree from the given array
code: import java . util . * ; class GFG { static int getMid ( int s , int e ) { return s + ( e - s ) / 2 ; } 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 int getMax ( int [ ] st , int n , int l , int r ) { if ( l < 0 r > n - 1 l > r ) { System . out . printf ( " Invalid ▁ Input " ) ; 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 ) { st [ si ] = arr [ ss ] ; return arr [ ss ] ; } 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 ) ) ) ; 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 [ ] = { 5 , 2 , 3 , 0 } ; int n = arr . length ; int [ ] st = constructST ( arr , n ) ; int [ ] [ ] Q = { { 1 , 3 } , { 0 , 2 } } ; for ( int i = 0 ; i < Q . length ; i ++ ) { int max = getMax ( st , n , Q [ i ] [ 0 ] , Q [ i ] [ 1 ] ) ; int ok = 0 ; for ( int j = 30 ; j >= 0 ; j -- ) { if ( ( max & ( 1 << j ) ) != 0 ) ok = 1 ; if ( ok <= 0 ) continue ; max |= ( 1 << j ) ; } System . out . print ( max + " ▁ " ) ; } } }