Levelwise Alternating OR and XOR operations in Segment Tree | Python3 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
import math NEW_LINE def getMid ( s , e ) : NEW_LINE INDENT return s + ( e - s ) // 2 NEW_LINE DEDENT def constructSTUtil ( arr , ss , se , st , si , operation ) : NEW_LINE INDENT if ( ss == se ) : NEW_LINE INDENT st [ si ] = arr [ ss ] NEW_LINE return NEW_LINE DEDENT mid = getMid ( ss , se ) NEW_LINE constructSTUtil ( arr , ss , mid , st , si * 2 + 1 , not operation ) NEW_LINE constructSTUtil ( arr , mid + 1 , se , st , si * 2 + 2 , not operation ) NEW_LINE if ( operation == 1 ) : NEW_LINE INDENT st [ si ] = ( st [ 2 * si + 1 ] st [ 2 * si + 2 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT st [ si ] = ( st [ 2 * si + 1 ] ^ st [ 2 * si + 2 ] ) NEW_LINE DEDENT DEDENT def constructST ( arr , n ) : NEW_LINE INDENT x = int ( math . ceil ( math . log2 ( n ) ) ) NEW_LINE max_size = 2 * int ( pow ( 2 , x ) ) - 1 NEW_LINE st = [ 0 ] * max_size NEW_LINE operationAtRoot = ( 0 if x % 2 == 0 else 1 ) NEW_LINE constructSTUtil ( arr , 0 , n - 1 , st , 0 , operationAtRoot ) NEW_LINE return st NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT leaves = [ 1 , 6 , 3 , 7 , 5 , 9 , 10 , 4 ] NEW_LINE n = len ( leaves ) NEW_LINE segmentTree = constructST ( leaves , n ) NEW_LINE rootIndex = 0 NEW_LINE print ( " Value ▁ at ▁ Root ▁ Node ▁ = ▁ " , segmentTree [ rootIndex ] ) NEW_LINE DEDENT