Number of subarrays have bitwise OR >= K | Python implementation of the approach ; Function to build the segment tree ; Function to return the bitwise OR of segment [ L . . R ] ; Function to return the count of required sub - arrays ; Build segment tree ; Query segment tree for bitwise OR of sub - array [ i . . j ] ; Driver code
N = 100002 NEW_LINE tree = [ 0 ] * ( 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 or q2 NEW_LINE DEDENT def countSubArrays ( arr , n , K ) : NEW_LINE INDENT build ( arr , 1 , 0 , n - 1 ) NEW_LINE count = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( n ) : NEW_LINE INDENT bitwise_or = query ( 1 , 0 , n - 1 , i , j ) NEW_LINE if bitwise_or >= K : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT DEDENT return count NEW_LINE DEDENT arr = [ 3 , 4 , 5 ] NEW_LINE n = len ( arr ) NEW_LINE k = 6 NEW_LINE print ( countSubArrays ( arr , n , k ) ) NEW_LINE