Range Query on array whose each element is XOR of index value and previous element | function return derived formula value . ; finding xor value of range [ y ... x ] ; function to solve query for l and r . ; if l or r is 0. ; finding x is divisible by 2 or not . ; Driver Code
< ? php function fun ( $ x ) { $ y = ( ( int ) ( $ x / 4 ) * 4 ) ; $ ans = 0 ; for ( $ i = $ y ; $ i <= $ x ; $ i ++ ) $ ans ^= $ i ; return $ ans ; } function query ( $ x ) { if ( $ x == 0 ) return 0 ; $ k = ( int ) ( ( $ x + 1 ) / 2 ) ; return ( $ x %= 2 ) ? 2 * fun ( $ k ) : ( ( fun ( $ k - 1 ) * 2 ) ^ ( $ k & 1 ) ) ; } function allQueries ( $ q , $ l , $ r ) { for ( $ i = 0 ; $ i < $ q ; $ i ++ ) echo ( query ( $ r [ $ i ] ) ^ query ( $ l [ $ i ] - 1 ) ) , " STRNEWLINE " ; } $ q = 3 ; $ l = array ( 2 , 2 , 5 ) ; $ r = array ( 4 , 8 , 9 ) ; allQueries ( $ q , $ l , $ r ) ; ? >