What exactly is XOR?

#1

I didn’t really understand what the purpose of the problem is, and how are we proceeding with it. It would be helpful if you could help me understand. Thank You!

#2

xor for a and b is according to this:
image

The question is asking us to look in the range 1 - 4. Here the indexing is 1 based. You thus look at the first 4 numbers and after the xors of each of them with 6, you can conclude that 6 has the maximum xor with the element 10. This is how 10 was returned.

Lets discuss the test case

5
0 3
0 5
0 10
0 6
1 1 4 6

Here 5 queries will be there and initially our array is empty
in frst 4 queries of type 0 we push into array
[3 5 10 6]
Then for last query of type 1 we get L=1,R=4 ,X=6
Now from the array we need to find a[i] in { a[L],a[L+1],…,a[R] } which gives max xor with X
Here { a[L],a[L+1],…,a[R] } == {a[1],a[2],a[3],a[4]} =={3,5,10,6}
and 3^6=5 , 5^6=3 ,10^6 =12 ,6^6=0
So 10 gives maximum xor so we print 10

There can be multiple queries of both the type and can be mixed like 0,0,0,1,0,1,0,0,0,1 … so on

#3

I got the crux of what XOR is, but still its really difficult to understand the given editorial solution for Range XOR, could you please guide me through it?

#4

Firstly you insert every number into the trie where every node is a bit, i.e, either 1 or 0. Also each node contains a vector which stores the indexes of the elements for which that particular bit is set. Thus when you make a query for range [l, r] and are given an integer x, you traverse the trie for the opposite bits which are present in x, because opposite bits at every position will maximize the xor value. Do the question max xor pair and you will be able to understand the concept behind this question.

If you face any difficulty, please feel free to revert back.

#5

Thank You , Max XOR value question was actually helpful to clear my doubts.