XOR of a submatrix queries | Javascript 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
var n = 3 ; function preComputeXor ( arr , prefix_xor ) { for ( i = 0 ; i < n ; i ++ ) for ( j = 0 ; j < n ; j ++ ) { if ( j == 0 ) prefix_xor [ i ] [ j ] = arr [ i ] [ j ] ; else prefix_xor [ i ] [ j ] = ( prefix_xor [ i ] [ j - 1 ] ^ arr [ i ] [ j ] ) ; } for ( i = 0 ; i < n ; i ++ ) for ( j = 1 ; j < n ; j ++ ) prefix_xor [ j ] [ i ] = ( prefix_xor [ j - 1 ] [ i ] ^ prefix_xor [ j ] [ i ] ) ; } function ansQuerie ( prefix_xor , x1 , y1 , x2 , y2 ) { var xor_1 = 0 , xor_2 = 0 , xor_3 = 0 ; if ( x1 != 0 ) xor_1 = prefix_xor [ x1 - 1 ] [ y2 ] ; if ( y1 != 0 ) xor_2 = prefix_xor [ x2 ] [ y1 - 1 ] ; if ( x1 != 0 && y1 != 0 ) xor_3 = prefix_xor [ x1 - 1 ] [ y1 - 1 ] ; return ( ( prefix_xor [ x2 ] [ y2 ] ^ xor_1 ) ^ ( xor_2 ^ xor_3 ) ) ; } var arr = [ [ 1 , 2 , 3 ] , [ 4 , 5 , 6 ] , [ 7 , 8 , 9 ] ] ; var prefix_xor = Array ( n ) ; for ( var i = 0 ; i < n ; i ++ ) prefix_xor [ i ] = Array ( n ) . fill ( 0 ) ; preComputeXor ( arr , prefix_xor ) ; document . write ( ansQuerie ( prefix_xor , 1 , 1 , 2 , 2 ) + " " ) ; document . write ( ansQuerie ( prefix_xor , 1 , 2 , 2 , 2 ) ) ;