Number of subarrays have bitwise OR >= K | Javascript 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
let N = 100002 ; let tree = new Array ( 4 * N ) ; function build ( arr , node , start , end ) { if ( start == end ) { tree [ node ] = arr [ start ] ; return ; } let mid = ( start + end ) >> 1 ; build ( arr , 2 * node , start , mid ) ; build ( arr , 2 * node + 1 , mid + 1 , end ) ; tree [ node ] = tree [ 2 * node ] | tree [ 2 * node + 1 ] ; } function query ( node , start , end , l , r ) { if ( start > end start > r end < l ) { return 0 ; } if ( start >= l && end <= r ) { return tree [ node ] ; } let mid = ( start + end ) >> 1 ; let q1 = query ( 2 * node , start , mid , l , r ) ; let q2 = query ( 2 * node + 1 , mid + 1 , end , l , r ) ; return q1 | q2 ; } function countSubArrays ( arr , n , K ) { build ( arr , 1 , 0 , n - 1 ) ; let count = 0 ; for ( let i = 0 ; i < n ; i ++ ) { for ( let j = i ; j < n ; j ++ ) { let bitwise_or = query ( 1 , 0 , n - 1 , i , j ) ; if ( bitwise_or >= K ) count ++ ; } } return count ; } let arr = [ 3 , 4 , 5 ] ; let n = arr . length ; let k = 6 ; document . write ( countSubArrays ( arr , n , k ) ) ;