Number of subarrays have bitwise OR >= K | Java implementation of 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 .
class GFG { static int N = 100002 ; static int tree [ ] = new int [ 4 * N ] ; static void build ( int [ ] arr , int node , int start , int end ) { if ( start == end ) { tree [ node ] = arr [ start ] ; return ; } int 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 ] ; } static int query ( int node , int start , int end , int l , int r ) { if ( start > end start > r end < l ) { return 0 ; } if ( start >= l && end <= r ) { return tree [ node ] ; } int mid = ( start + end ) >> 1 ; int q1 = query ( 2 * node , start , mid , l , r ) ; int q2 = query ( 2 * node + 1 , mid + 1 , end , l , r ) ; return q1 | q2 ; } static int countSubArrays ( int [ ] arr , int n , int K ) { int count = 0 ; for ( int i = 0 ; i < n ; i ++ ) { int low = i , high = n - 1 , index = Integer . MAX_VALUE ; while ( low <= high ) { int mid = ( low + high ) >> 1 ; if ( query ( 1 , 0 , n - 1 , i , mid ) >= K ) { index = Math . min ( index , mid ) ; high = mid - 1 ; } else { low = mid + 1 ; } } if ( index != Integer . MAX_VALUE ) { count += n - index ; } } return count ; } public static void main ( String [ ] args ) { int arr [ ] = { 3 , 4 , 5 } ; int n = arr . length ; build ( arr , 1 , 0 , n - 1 ) ; int k = 6 ; System . out . println ( countSubArrays ( arr , n , k ) ) ; } }