Levelwise Alternating OR and XOR operations in Segment Tree | Java program to build levelwise OR / XOR alternating Segment tree ; A utility function to get the middle index from corner indexes . ; A recursive function that constructs Segment Tree for array [ ss . . se ] . si is index of current node in segment tree st operation denotes which operation is carried out at that level to merge the left and right child . It 's either 0 or 1. ; 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 sum of values in this node ; Build the left and the right subtrees by using the fact that operation at level ( i + 1 ) = ! ( operation at level i ) ; Merge the left and right subtrees by checking the operation to be carried . If operation = 1 , then do OR else XOR ; OR operation ; XOR operation ; Function to construct segment tree from given array . This function allocates memory for segment tree and calls constructSTUtil ( ) to fill the allocated memory ; Height of segment tree ; Maximum size of segment tree ; Allocate memory ; Operation = 1 ( XOR ) if Height of tree is even else it is 0 ( OR ) for the root node ; Fill the allocated memory st ; Return the constructed segment tree ; Driver Code ; Leaf nodes ; Build the segment tree ; Root node is at index 0 considering 0 - based indexing in segment Tree ; Print value at rootIndex
class GFG { static int getMid ( int s , int e ) { return s + ( e - s ) / 2 ; } static void constructSTUtil ( int arr [ ] , int ss , int se , int st [ ] , int si , boolean operation ) { if ( ss == se ) { st [ si ] = arr [ ss ] ; return ; } int mid = getMid ( ss , se ) ; constructSTUtil ( arr , ss , mid , st , si * 2 + 1 , ! operation ) ; constructSTUtil ( arr , mid + 1 , se , st , si * 2 + 2 , ! operation ) ; if ( operation ) { st [ si ] = ( st [ 2 * si + 1 ] st [ 2 * si + 2 ] ) ; } else { st [ si ] = ( st [ 2 * si + 1 ] ^ st [ 2 * si + 2 ] ) ; } } 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 ] ; boolean operationAtRoot = ! ( x % 2 == 0 ) ; constructSTUtil ( arr , 0 , n - 1 , st , 0 , operationAtRoot ) ; return st ; } public static void main ( String [ ] args ) { int leaves [ ] = { 1 , 6 , 3 , 7 , 5 , 9 , 10 , 4 } ; int n = leaves . length ; int [ ] segmentTree = constructST ( leaves , n ) ; int rootIndex = 0 ; System . out . println ( " Value ▁ at ▁ Root ▁ Node ▁ = ▁ " + segmentTree [ rootIndex ] ) ; } }