Queries on XOR of greatest odd divisor of the range | Precompute the prefix XOR of greatest odd divisor ; Finding the Greatest Odd divisor ; Finding prefix XOR ; Return XOR of the range ; Driver code
function prefixXOR ( arr , preXOR , n ) { for ( let i = 0 ; i < n ; i ++ ) { while ( arr [ i ] % 2 != 1 ) arr [ i ] = parseInt ( arr [ i ] / 2 ) ; preXOR [ i ] = arr [ i ] ; } for ( let i = 1 ; i < n ; i ++ ) preXOR [ i ] = preXOR [ i - 1 ] ^ preXOR [ i ] ; } function query ( preXOR , l , r ) { if ( l == 0 ) return preXOR [ r ] ; else return preXOR [ r ] ^ preXOR [ l - 1 ] ; } let arr = [ 3 , 4 , 5 ] ; let n = arr . length ; let preXOR = new Array ( n ) ; prefixXOR ( arr , preXOR , n ) ; document . write ( query ( preXOR , 0 , 2 ) + " " ) ; document . write ( query ( preXOR , 1 , 2 ) + " " ) ;