Range Query on array whose each element is XOR of index value and previous element | Java Program to solve 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 . ; Driven Program
import java . io . * ; class GFG { static int fun ( int x ) { int y = ( x / 4 ) * 4 ; int ans = 0 ; for ( int i = y ; i <= x ; i ++ ) ans ^= i ; return ans ; } static int query ( int x ) { if ( x == 0 ) return 0 ; int k = ( x + 1 ) / 2 ; return ( ( x %= 2 ) != 0 ) ? 2 * fun ( k ) : ( ( fun ( k - 1 ) * 2 ) ^ ( k & 1 ) ) ; } static void allQueries ( int q , int l [ ] , int r [ ] ) { for ( int i = 0 ; i < q ; i ++ ) System . out . println ( ( query ( r [ i ] ) ^ query ( l [ i ] - 1 ) ) ) ; } public static void main ( String [ ] args ) { int q = 3 ; int [ ] l = { 2 , 2 , 5 } ; int [ ] r = { 4 , 8 , 9 } ; allQueries ( q , l , r ) ; } }