Queries for bitwise OR in the given matrix | Python 3 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 with ith bit set is greater than 0 ; Driver code
bitscount = 32 NEW_LINE n = 3 NEW_LINE prefix_count = [ [ [ 0 for i in range ( n ) ] for j in range ( n ) ] for k in range ( bitscount ) ] NEW_LINE def findPrefixCount ( arr ) : NEW_LINE INDENT for i in range ( bitscount ) : NEW_LINE INDENT for j in range ( n ) : NEW_LINE INDENT prefix_count [ i ] [ j ] [ 0 ] = ( ( arr [ j ] [ 0 ] >> i ) & 1 ) NEW_LINE for k in range ( 1 , n ) : NEW_LINE INDENT prefix_count [ i ] [ j ] [ k ] = ( ( arr [ j ] [ k ] >> i ) & 1 ) NEW_LINE prefix_count [ i ] [ j ] [ k ] += prefix_count [ i ] [ j ] [ k - 1 ] NEW_LINE DEDENT DEDENT DEDENT for i in range ( bitscount ) : NEW_LINE INDENT for j in range ( 1 , n ) : NEW_LINE INDENT for k in range ( n ) : NEW_LINE INDENT prefix_count [ i ] [ j ] [ k ] += prefix_count [ i ] [ j - 1 ] [ k ] NEW_LINE DEDENT DEDENT DEDENT DEDENT def rangeOr ( x1 , y1 , x2 , y2 ) : NEW_LINE INDENT ans = 0 NEW_LINE for i in range ( bitscount ) : NEW_LINE INDENT if ( x1 == 0 and y1 == 0 ) : NEW_LINE INDENT p = prefix_count [ i ] [ x2 ] [ y2 ] NEW_LINE DEDENT elif ( x1 == 0 ) : NEW_LINE INDENT p = prefix_count [ i ] [ x2 ] [ y2 ] - prefix_count [ i ] [ x2 ] [ y1 - 1 ] NEW_LINE DEDENT elif ( y1 == 0 ) : NEW_LINE INDENT p = prefix_count [ i ] [ x2 ] [ y2 ] - prefix_count [ i ] [ x1 - 1 ] [ y2 ] NEW_LINE DEDENT else : NEW_LINE INDENT 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 ] ; NEW_LINE DEDENT if ( p != 0 ) : NEW_LINE INDENT ans = ( ans | ( 1 << i ) ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ [ 1 , 2 , 3 ] , [ 4 , 5 , 6 ] , [ 7 , 8 , 9 ] ] NEW_LINE findPrefixCount ( arr ) NEW_LINE queries = [ [ 1 , 1 , 1 , 1 ] , [ 1 , 2 , 2 , 2 ] ] NEW_LINE q = len ( queries ) NEW_LINE for i in range ( q ) : NEW_LINE INDENT print ( rangeOr ( queries [ i ] [ 0 ] , queries [ i ] [ 1 ] , queries [ i ] [ 2 ] , queries [ i ] [ 3 ] ) ) NEW_LINE DEDENT DEDENT