Queries for bitwise AND in the given matrix | C ++ 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
#include <bits/stdc++.h> NEW_LINE #define bitscount  32 NEW_LINE #define n  3 NEW_LINE using namespace std ; int prefix_count [ bitscount ] [ n ] [ n ] ; void findPrefixCount ( int arr [ ] [ n ] ) { for ( int i = 0 ; i < bitscount ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { prefix_count [ i ] [ j ] [ 0 ] = ( ( arr [ j ] [ 0 ] >> i ) & 1 ) ; for ( int 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 ( int i = 0 ; i < bitscount ; i ++ ) for ( int j = 1 ; j < n ; j ++ ) for ( int k = 0 ; k < n ; k ++ ) prefix_count [ i ] [ j ] [ k ] += prefix_count [ i ] [ j - 1 ] [ k ] ; } int rangeAnd ( int x1 , int y1 , int x2 , int y2 ) { int ans = 0 ; for ( int i = 0 ; i < bitscount ; i ++ ) { int p ; if ( x1 == 0 and 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 ; } int main ( ) { int arr [ ] [ n ] = { { 1 , 2 , 3 } , { 4 , 5 , 6 } , { 7 , 8 , 9 } } ; findPrefixCount ( arr ) ; int queries [ ] [ 4 ] = { { 1 , 1 , 1 , 1 } , { 1 , 2 , 2 , 2 } } ; int q = sizeof ( queries ) / sizeof ( queries [ 0 ] ) ; for ( int i = 0 ; i < q ; i ++ ) cout << rangeAnd ( queries [ i ] [ 0 ] , queries [ i ] [ 1 ] , queries [ i ] [ 2 ] , queries [ i ] [ 3 ] ) << endl ; return 0 ; }