Range xor using trie

#1


kidnly modify

#2

Hey @Vibhuti0206,

While solving this question using trie.

  1. At each node of the trie, we will store the ith bit of the number for a query of type 0.
  2. To solve the query of type 1 we will store the indexes of the number that pass through that node.
  3. When we go down the tree during a query and maximizing the xor, we go in a direction that contains at least one index in range L to R, otherwise, we will go in the other direction.
  4. To search if at least one index is within the stored indexes we will use binary search.
    (Since the indices will always be positive, you can apply count sort on them. That will do your work in linear time.)

Now, keeping above in mind, try to correct your code.

Hope, this would help.
Give a like if you are satisfied.

#3

could not understand,could you please elaborate point 2 n 3

#4

Sure @Vibhuti0206,

Point 2:
Store the list of indexes of the elements of the array that passes through a certain node.
Example:
for 5=101, the tree would be:
_________root
________________1
____________0
________________1

inserting 7=111 to it, the tree will become
_________root
_________________1
____________0_________1
________________1 ________1

As the first bit of both 5 and 7 passes through a node with value 1. So, maintain a list of indexes at each node containing the indexes of the elements that pass through that particular node.

Point 3:
Above will help in identifying whether a particular bit belongs to any element between the range L and R. Thus, making the entire process efficient.

Let me know if you still don’t understand.