Number of subarrays have bitwise OR >= K | C ++ 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 .
#include <bits/stdc++.h> NEW_LINE #define N  100002 NEW_LINE using namespace std ; int tree [ 4 * N ] ; 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 ] ; } 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 ; } int countSubArrays ( const int * arr , int n , int K ) { int count = 0 ; for ( int i = 0 ; i < n ; i ++ ) { int low = i , high = n - 1 , index = INT_MAX ; while ( low <= high ) { int mid = ( low + high ) >> 1 ; if ( query ( 1 , 0 , n - 1 , i , mid ) >= K ) { index = min ( index , mid ) ; high = mid - 1 ; } else { low = mid + 1 ; } } if ( index != INT_MAX ) { count += n - index ; } } return count ; } int main ( ) { int arr [ ] = { 3 , 4 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; build ( arr , 1 , 0 , n - 1 ) ; int k = 6 ; cout << countSubArrays ( arr , n , k ) ; return 0 ; }