XOR of a submatrix queries | Python implementation of the approach ; Function to pre - compute the xor ; Left to right prefix xor for each row ; Top to bottom prefix xor for each column ; Function to process the queries x1 , x2 , y1 , y2 represent the positions of the top - left and bottom right corners ; To store the xor values ; Finding the values we need to xor with value at ( x2 , y2 ) in prefix - xor matrix ; Return the required prefix xor ; Driver code ; To store pre - computed xor ; Pre - computing xor ; Queries
n = 3 NEW_LINE def preComputeXor ( arr , prefix_xor ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT for j in range ( n ) : NEW_LINE INDENT if ( j == 0 ) : NEW_LINE INDENT prefix_xor [ i ] [ j ] = arr [ i ] [ j ] NEW_LINE DEDENT else : NEW_LINE INDENT prefix_xor [ i ] [ j ] = ( prefix_xor [ i ] [ j - 1 ] ^ arr [ i ] [ j ] ) NEW_LINE DEDENT DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT for j in range ( 1 , n ) : NEW_LINE INDENT prefix_xor [ j ] [ i ] = ( prefix_xor [ j - 1 ] [ i ] ^ prefix_xor [ j ] [ i ] ) NEW_LINE DEDENT DEDENT DEDENT def ansQuerie ( prefix_xor , x1 , y1 , x2 , y2 ) : NEW_LINE INDENT xor_1 , xor_2 , xor_3 = 0 , 0 , 0 NEW_LINE if ( x1 != 0 ) : NEW_LINE INDENT xor_1 = prefix_xor [ x1 - 1 ] [ y2 ] NEW_LINE DEDENT if ( y1 != 0 ) : NEW_LINE INDENT xor_2 = prefix_xor [ x2 ] [ y1 - 1 ] NEW_LINE DEDENT if ( x1 != 0 and y1 != 0 ) : NEW_LINE INDENT xor_3 = prefix_xor [ x1 - 1 ] [ y1 - 1 ] NEW_LINE DEDENT return ( ( prefix_xor [ x2 ] [ y2 ] ^ xor_1 ) ^ ( xor_2 ^ xor_3 ) ) NEW_LINE DEDENT arr = [ [ 1 , 2 , 3 ] , [ 4 , 5 , 6 ] , [ 7 , 8 , 9 ] ] NEW_LINE prefix_xor = [ [ 0 for i in range ( n ) ] for i in range ( n ) ] NEW_LINE preComputeXor ( arr , prefix_xor ) NEW_LINE print ( ansQuerie ( prefix_xor , 1 , 1 , 2 , 2 ) ) NEW_LINE print ( ansQuerie ( prefix_xor , 1 , 2 , 2 , 2 ) ) NEW_LINE