Find array sum using Bitwise OR after splitting given array in two halves after K circular shifts | Python3 program to find Bitwise OR of two equal halves of an array after performing K right circular shifts ; Array for storing the segment tree ; Function to build the segment tree ; Function to return the OR of elements in the range [ l , r ] ; Check for out of bound condition ; Find middle of the range ; Recurse for all the elements in array ; Function to find the OR sum ; Function to build the segment Tree ; Loop to handle q queries ; Effective number of right circular shifts ; OR of second half of the array [ n / 2 - i , n - 1 - i ] ; OR of first half of the array [ n - i , n - 1 ] OR [ 0 , n / 2 - 1 - i ] ; Print final answer to the query ; Driver Code
MAX = 100005 NEW_LINE seg = [ 0 ] * ( 4 * MAX ) NEW_LINE def build ( node , l , r , a ) : NEW_LINE INDENT if ( l == r ) : NEW_LINE INDENT seg [ node ] = a [ l ] NEW_LINE DEDENT else : NEW_LINE INDENT mid = ( l + r ) // 2 NEW_LINE build ( 2 * node , l , mid , a ) NEW_LINE build ( 2 * node + 1 , mid + 1 , r , a ) NEW_LINE seg [ node ] = ( seg [ 2 * node ] seg [ 2 * node + 1 ] ) NEW_LINE DEDENT DEDENT def query ( node , l , r , start , end , a ) : NEW_LINE INDENT if ( l > end or r < start ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( start <= l and r <= end ) : NEW_LINE INDENT return seg [ node ] NEW_LINE DEDENT mid = ( l + r ) // 2 NEW_LINE return ( ( query ( 2 * node , l , mid , start , end , a ) ) | ( query ( 2 * node + 1 , mid + 1 , r , start , end , a ) ) ) NEW_LINE DEDENT def orsum ( a , n , q , k ) : NEW_LINE INDENT build ( 1 , 0 , n - 1 , a ) NEW_LINE for j in range ( q ) : NEW_LINE INDENT i = k [ j ] % ( n // 2 ) NEW_LINE sec = query ( 1 , 0 , n - 1 , n // 2 - i , n - i - 1 , a ) NEW_LINE first = ( query ( 1 , 0 , n - 1 , 0 , n // 2 - 1 - i , a ) | query ( 1 , 0 , n - 1 , n - i , n - 1 , a ) ) NEW_LINE temp = sec + first NEW_LINE print ( temp ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 7 , 44 , 19 , 86 , 65 , 39 , 75 , 101 ] NEW_LINE n = len ( a ) NEW_LINE q = 2 NEW_LINE k = [ 4 , 2 ] NEW_LINE orsum ( a , n , q , k ) NEW_LINE DEDENT