How does the folllowing relation hold??
F(L,R)=F(1,R) XOR F(1,L-1)
where F(x,y) denotes the xor of range l-r
1 Like
We can write out a few examples to see why it works. Let us denote the integers we are considering a[1], a[2], …, a[n], then denote F(i) := a[1] xor a[2] xor … a[n].
An example n = 10. Suppose we want to know the xored value in the range [3, 7], then we know it is just (a[3] xor a[4] xor a[5] xor a[6] xor a[7]). Alright, let us use the formula you have provided us. F(7) xor F(2) = (a[1] xor a[2] xor a[3] xor a[4] xor a[5] xor a[6] xor a[7]) xor (a[1] xor a[2]). It should be clear, that a number y xored with itself will be 0 (i.e. y xor y = 0). Since the xor operation is commutative, we can reorder the whole expression a little bit. (a[1] xor a[1]) xor (a[2] xor a[2]) xor …
and we gain what we wanted.
4 Likes