Queries for bitwise OR in the index range [ L , R ] of the given array | PHP 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
< ? php $ MAX = 100000 ; $ bitscount = 32 ; $ prefix_count = array_fill ( 0 , $ bitscount , array_fill ( 0 , $ MAX , NULL ) ) ; function findPrefixCount ( & $ arr , $ n ) { global $ MAX , $ bitscount , $ prefix_count ; for ( $ i = 0 ; $ i < $ bitscount ; $ i ++ ) { $ prefix_count [ $ i ] [ 0 ] = ( ( $ arr [ 0 ] >> $ i ) & 1 ) ; for ( $ 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 ) { global $ MAX , $ bitscount , $ prefix_count ; $ ans = 0 ; for ( $ i = 0 ; $ i < $ bitscount ; $ i ++ ) { 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 ; } $ arr = array ( 7 , 5 , 3 , 5 , 2 , 3 ) ; $ n = sizeof ( $ arr ) / sizeof ( $ arr [ 0 ] ) ; findPrefixCount ( $ arr , $ n ) ; $ queries = array ( array ( 1 , 3 ) , array ( 4 , 5 ) ) ; $ q = sizeof ( $ queries ) / sizeof ( $ queries [ 0 ] ) ; for ( $ i = 0 ; $ i < $ q ; $ i ++ ) echo rangeOr ( $ queries [ $ i ] [ 0 ] , $ queries [ $ i ] [ 1 ] ) . " STRNEWLINE " ; return 0 ; ? >