Leftover element after performing alternate Bitwise OR and Bitwise XOR operations on adjacent pairs | Python3 program to print the Leftover element after performing alternate Bitwise OR and Bitwise XOR operations to the pairs . ; array to store the tree ; array to store the level of every parent ; function to construct the tree ; level of child is always 0 ; Recursive call ; Increase the level of every parent , which is level of child + 1 ; If the parent is at odd level , then do a bitwise OR ; If the parent is at even level , then do a bitwise XOR ; Function that updates the tree ; If it is a leaf and the leaf which is to be updated ; out of range ; not a leaf then recurse ; recursive call ; check if the parent is at odd or even level and perform OR or XOR according to that ; Function that assigns value to a [ index ] and calls update function to update the tree ; Driver Code ; builds the tree ; 1 st query ; 2 nd query
N = 1000 NEW_LINE tree = [ None ] * N NEW_LINE level = [ None ] * N NEW_LINE def constructTree ( low , high , pos , a ) : NEW_LINE INDENT if low == high : NEW_LINE INDENT level [ pos ] , tree [ pos ] = 0 , a [ high ] NEW_LINE return NEW_LINE DEDENT mid = ( low + high ) // 2 NEW_LINE constructTree ( low , mid , 2 * pos + 1 , a ) NEW_LINE constructTree ( mid + 1 , high , 2 * pos + 2 , a ) NEW_LINE level [ pos ] = level [ 2 * pos + 1 ] + 1 NEW_LINE if level [ pos ] & 1 : NEW_LINE INDENT tree [ pos ] = tree [ 2 * pos + 1 ] | tree [ 2 * pos + 2 ] NEW_LINE DEDENT else : NEW_LINE INDENT tree [ pos ] = tree [ 2 * pos + 1 ] ^ tree [ 2 * pos + 2 ] NEW_LINE DEDENT DEDENT def update ( low , high , pos , index , a ) : NEW_LINE INDENT if low == high and low == index : NEW_LINE INDENT tree [ pos ] = a [ low ] NEW_LINE return NEW_LINE DEDENT if index < low or index > high : NEW_LINE INDENT return NEW_LINE DEDENT if low != high : NEW_LINE INDENT mid = ( low + high ) // 2 NEW_LINE update ( low , mid , 2 * pos + 1 , index , a ) NEW_LINE update ( mid + 1 , high , 2 * pos + 2 , index , a ) NEW_LINE if level [ pos ] & 1 : NEW_LINE INDENT tree [ pos ] = tree [ 2 * pos + 1 ] | tree [ 2 * pos + 2 ] NEW_LINE DEDENT else : NEW_LINE INDENT tree [ pos ] = tree [ 2 * pos + 1 ] ^ tree [ 2 * pos + 2 ] NEW_LINE DEDENT DEDENT DEDENT def updateValue ( index , value , a , n ) : NEW_LINE INDENT a [ index ] = value NEW_LINE update ( 0 , n - 1 , 0 , index , a ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 1 , 4 , 5 , 6 ] NEW_LINE n = len ( a ) NEW_LINE constructTree ( 0 , n - 1 , 0 , a ) NEW_LINE index , value = 0 , 2 NEW_LINE updateValue ( index , value , a , n ) NEW_LINE print ( tree [ 0 ] ) NEW_LINE index , value = 3 , 5 NEW_LINE updateValue ( index , value , a , n ) NEW_LINE print ( tree [ 0 ] ) NEW_LINE DEDENT