Queries for bitwise OR in the index range [ L , R ] of the given array | Javascript implementation of the approach ; Array to store bit - wise prefix count ; Function to find the prefix sum ; Loop for each bit ; Loop to find prefix count ; Function to answer query ; To store the answer ; Loop for each bit ; To store the number of variables with ith bit set ; Condition for ith bit of answer to be set ; Driver code
let MAX = 100000 ; let bitscount = 32 ; let prefix_count = new Array ( bitscount ) ; for ( let i = 0 ; i < bitscount ; i ++ ) { prefix_count [ i ] = new Array ( MAX ) ; for ( let j = 0 ; j < MAX ; j ++ ) { prefix_count [ i ] [ j ] = 0 ; } } function findPrefixCount ( arr , n ) { for ( let i = 0 ; i < bitscount ; i ++ ) { prefix_count [ i ] [ 0 ] = ( ( arr [ 0 ] >> i ) & 1 ) ; for ( let j = 1 ; j < n ; j ++ ) { prefix_count [ i ] [ j ] = ( ( arr [ j ] >> i ) & 1 ) ; prefix_count [ i ] [ j ] += prefix_count [ i ] [ j - 1 ] ; } } } function rangeOr ( l , r ) { let ans = 0 ; for ( let i = 0 ; i < bitscount ; i ++ ) { let x ; if ( l == 0 ) x = prefix_count [ i ] [ r ] ; else x = prefix_count [ i ] [ r ] - prefix_count [ i ] [ l - 1 ] ; if ( x != 0 ) ans = ( ans | ( 1 << i ) ) ; } return ans ; } let arr = [ 7 , 5 , 3 , 5 , 2 , 3 ] ; let n = arr . length ; findPrefixCount ( arr , n ) ; let queries = [ [ 1 , 3 ] , [ 4 , 5 ] ] ; let q = queries . length ; for ( let i = 0 ; i < q ; i ++ ) document . write ( rangeOr ( queries [ i ] [ 0 ] , queries [ i ] [ 1 ] ) + " " ) ;