XOR of a submatrix queries | PHP 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
< ? php $ n = 3 ; function preComputeXor ( $ arr , & $ prefix_xor ) { global $ n ; 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 ) { $ xor_1 = $ xor_2 = $ 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 and $ y1 != 0 ) $ xor_3 = $ prefix_xor [ $ x1 - 1 ] [ $ y1 - 1 ] ; return ( ( $ prefix_xor [ $ x2 ] [ $ y2 ] ^ $ xor_1 ) ^ ( $ xor_2 ^ $ xor_3 ) ) ; } $ arr = array ( array ( 1 , 2 , 3 ) , array ( 4 , 5 , 6 ) , array ( 7 , 8 , 9 ) ) ; $ prefix_xor = array_fill ( 0 , $ n , array_fill ( 0 , $ n , 0 ) ) ; preComputeXor ( $ arr , $ prefix_xor ) ; echo ansQuerie ( $ prefix_xor , 1 , 1 , 2 , 2 ) . " " ; echo ansQuerie ( $ prefix_xor , 1 , 2 , 2 , 2 ) ; ? >