Well if you want to find answer for some a[i] 0<=i<n then put in trie all a[j] such j<i.

And for each i calculate what is the maximum possible xor with trie. Then add that a[i] to trie.

This problem can be solved using binary trie.

First calculate the prefix xor of the array i.e. pre[0] = 0; pre[i] = pre[i — 1] ^ a[i]; (1 <= i <= n)

Now we know that the xor sum of a range [l, r] will be pre[r] ^ pre[l — 1].

So, firstly insert 0 in your trie. Now for each i in range [1, n], check for pre[i] the maximum xor pair that you can find out in your trie and let's call it t[i]. So, the answer will be max over all such pre[i] ^ t[i].

By maximum xor pair of pre[i] i.e. t[i], I mean, the number such that among all the numbers that are inserted in the trie, pre[i] ^ (that number) should be maximum.

How to find out t[i] ?

It's actually very simple. Build a binary trie. Now, for finding the max xor pair, you need to go over all the bits of pre[i] starting from the Most Significant Bit and if it's set then we'll try to find a number(from trie), with this bit off, and if it's off, then we'll try to find a number with this bit on. Thus guaranteeing us the maximum xor pair.

Do a prefix xor on the array. A subarray in the previous context is now either a single element in this context, or a xor of 2 elements, and you want the maximum of those. We can find for each element in the array, another element in the array that gives maximal xor with it, and you can do it with a trie:

Build a trie, where each number in the array is inserted by its bits, starting from the most significant to the least significant. Now suppose this trie is given an integer X and you want to find the best element in the trie to xor it with. Iterate over the bits of X from the most significant, and also keep the node T in the trie you're currently on (initially the root). if the next most significant bit is 1/0, then you want to check if T has any children from edge 0/1. If there is you go by that edge, otherwise you go by the opposite edge.

So you do this with each element in the array, get the maximum of those and compare it with the maximum of the array.

A related problem 617E - XOR and Favorite Number

Thank you all!

Do checkout this one : Tutorial-on-Trie-and-example-problems

Link