Queries for bitwise AND in the given matrix | 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 for each row ; Finding column - wise prefix count ; Function to return the result for a query ; To store the answer ; Loop for each bit ; To store the number of variables with ith bit set ; If count of variables whose ith bit is set equals to the total elements in the sub - matrix ; Driver code
let bitscount = 32 ; let n = 3 ; let prefix_count = new Array ( bitscount ) ; for ( let i = 0 ; i < bitscount ; i ++ ) { prefix_count [ i ] = new Array ( n ) ; for ( let j = 0 ; j < n ; j ++ ) { prefix_count [ i ] [ j ] = new Array ( n ) ; for ( let k = 0 ; k < n ; k ++ ) { prefix_count [ i ] [ j ] [ k ] = 0 ; } } } function findPrefixCount ( arr ) { for ( let i = 0 ; i < bitscount ; i ++ ) { for ( let j = 0 ; j < n ; j ++ ) { prefix_count [ i ] [ j ] [ 0 ] = ( ( arr [ j ] [ 0 ] >> i ) & 1 ) ; for ( let k = 1 ; k < n ; k ++ ) { prefix_count [ i ] [ j ] [ k ] = ( ( arr [ j ] [ k ] >> i ) & 1 ) ; prefix_count [ i ] [ j ] [ k ] += prefix_count [ i ] [ j ] [ k - 1 ] ; } } } for ( let i = 0 ; i < bitscount ; i ++ ) for ( let j = 1 ; j < n ; j ++ ) for ( let k = 0 ; k < n ; k ++ ) prefix_count [ i ] [ j ] [ k ] += prefix_count [ i ] [ j - 1 ] [ k ] ; } function rangeAnd ( x1 , y1 , x2 , y2 ) { let ans = 0 ; for ( let i = 0 ; i < bitscount ; i ++ ) { let p ; if ( x1 == 0 && y1 == 0 ) p = prefix_count [ i ] [ x2 ] [ y2 ] ; else if ( x1 == 0 ) p = prefix_count [ i ] [ x2 ] [ y2 ] - prefix_count [ i ] [ x2 ] [ y1 - 1 ] ; else if ( y1 == 0 ) p = prefix_count [ i ] [ x2 ] [ y2 ] - prefix_count [ i ] [ x1 - 1 ] [ y2 ] ; else p = prefix_count [ i ] [ x2 ] [ y2 ] - prefix_count [ i ] [ x1 - 1 ] [ y2 ] - prefix_count [ i ] [ x2 ] [ y1 - 1 ] + prefix_count [ i ] [ x1 - 1 ] [ y1 - 1 ] ; if ( p == ( x2 - x1 + 1 ) * ( y2 - y1 + 1 ) ) ans = ( ans | ( 1 << i ) ) ; } return ans ; } let arr = [ [ 1 , 2 , 3 ] , [ 4 , 5 , 6 ] , [ 7 , 8 , 9 ] ] ; findPrefixCount ( arr ) ; let queries = [ [ 1 , 1 , 1 , 1 ] , [ 1 , 2 , 2 , 2 ] ] ; let q = queries . length ; for ( let i = 0 ; i < q ; i ++ ) document . write ( rangeAnd ( queries [ i ] [ 0 ] , queries [ i ] [ 1 ] , queries [ i ] [ 2 ] , queries [ i ] [ 3 ] ) + " " ) ;