Number of subarrays have bitwise OR >= K | Python3 program to implement the above approach ; Function which builds the segment tree ; Function that returns bitwise OR of segment [ L . . R ] ; Function to count requisite number of subarrays ; Check for subarrays starting with index i ; If OR of subarray [ i . . mid ] >= K , then all subsequent subarrays will have OR >= K therefore reduce high to mid - 1 to find the minimal length subarray [ i . . mid ] having OR >= K ; Increase count with number of subarrays having OR >= K and starting with index i ; Driver code ; Build segment tree .
N = 100002 NEW_LINE tree = [ 0 for i in range ( 4 * N ) ] ; NEW_LINE def build ( arr , node , start , end ) : NEW_LINE INDENT if ( start == end ) : NEW_LINE INDENT tree [ node ] = arr [ start ] ; NEW_LINE return ; NEW_LINE DEDENT mid = ( start + end ) >> 1 ; NEW_LINE build ( arr , 2 * node , start , mid ) ; NEW_LINE build ( arr , 2 * node + 1 , mid + 1 , end ) ; NEW_LINE tree [ node ] = tree [ 2 * node ] | tree [ 2 * node + 1 ] ; NEW_LINE DEDENT def query ( node , start , end , l , r ) : NEW_LINE INDENT if ( start > end or start > r or end < l ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( start >= l and end <= r ) : NEW_LINE INDENT return tree [ node ] ; NEW_LINE DEDENT mid = ( start + end ) >> 1 ; NEW_LINE q1 = query ( 2 * node , start , mid , l , r ) ; NEW_LINE q2 = query ( 2 * node + 1 , mid + 1 , end , l , r ) ; NEW_LINE return q1 | q2 ; NEW_LINE DEDENT def countSubArrays ( arr , n , K ) : NEW_LINE INDENT count = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT low = i NEW_LINE high = n - 1 NEW_LINE index = 1000000000 NEW_LINE while ( low <= high ) : NEW_LINE INDENT mid = ( low + high ) >> 1 ; NEW_LINE if ( query ( 1 , 0 , n - 1 , i , mid ) >= K ) : NEW_LINE INDENT index = min ( index , mid ) ; NEW_LINE high = mid - 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT low = mid + 1 ; NEW_LINE DEDENT DEDENT if ( index != 1000000000 ) : NEW_LINE INDENT count += n - index ; NEW_LINE DEDENT DEDENT return count ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 3 , 4 , 5 ] NEW_LINE n = len ( arr ) NEW_LINE build ( arr , 1 , 0 , n - 1 ) ; NEW_LINE k = 6 ; NEW_LINE print ( countSubArrays ( arr , n , k ) ) NEW_LINE DEDENT