Find the subarray with the max XOR from an array (using a trie)

Question

The problem statement is:

Given an array of integers, find the subarray with maximum XOR.

Some examples are:

Input: arr[] = {1, 2, 3, 4}
Output: 7
The subarray {3, 4} has maximum XOR value

Input: arr[] = {8, 1, 2, 12, 7, 6}
Output: 15
The subarray {1, 2, 12} has maximum XOR value

I found a quora post which provides an explanation of the solution to the problem but I'm not quite able to fully understand what is being explained.

The post starts by introducing a similar problem to the one above (problem 1 in the post):

Given an array of integers, we have to find two elements whose XOR is maximum

It then describes a trie data structure which can handle two types of queries:

1. Insert a number X
2. Given a Y, find maximum XOR of Y with all numbers that have been inserted till now. If we have this data structure, we'll insert integers as we go, and with query of 2nd type we'll find the maximum XOR

The above image handles query type 1. For query type 2, the post has the following:

Let's say our number Y is b1,b2...bn, where b1,b2.. are binary bits. We start from b1. Now for the XOR to be maximum, we'll try to make most significant bit 1 after taking XOR. So, if b1 is 0, we'll need a 1 and vice versa. In the trie, we go to the required bit side. If favorable option is not there, we'll go other side. Doing this all over for i=1 to n, we'll get the maximum XOR possible.

There are a few points of confusion here. One is: how exactly is the trie being used to find the two elements which have the max XOR up to the current point in the array? It seems that they are saying something like this:

e.g. array= {1,2,3,4}, current number is 3 -> 0011 (4 bit representation) meaning 1 and 2 have already been inserted into the trie. Up to this point the max xor should be of numbers 1 and 2 (which yields 3). With the approach provided in the post, it seems that the max xor could be stored in a variable so that by the time the last number in the array is xored with the current stat of the trie (which I'm assuming would have had elements 1,2, and 3 inserted already), the variable would have the max so far. But how would the algorithm store which two elements have been xor to yield that max?

Finally, the logic from this approach is supposed to be applied to the problem (problem 2 in the post):

Given an array of integers, find the subarray with maximum XOR

Here, the following solution was provided:

Let's say F(L,R) is XOR of subarray from L to R. Here we use the property that F(L,R)=F(1,R) XOR F(1,L-1). How? Let's say our subarray with maximum XOR ended at position i. Now, we need to maximise F(L,i) ie. F(1,i) XOR F(1,L-1) where L<=i. Suppose, we inserted F(1,L-1) in our trie for all L<=i, then it's just problem 1.

I don't really understand the property that F(L,R)=F(1,R) XOR F(1,L-1). I'm assuming here that R is the right bound of the max subarray whereas L would be its left bound, but its not clear why F(1,i) would need to be XOR'ed with F(1,L-1). And from this, how would the logic from problem 1 apply here?

I realized that this question is long, but as the problem is multi-faceted it seemed necessary to include these essential parts of the question.

Answer 1

The first question: when you add an element to a trie, you can store additional information in the leaf indicating the index of the element in the array. When you traverse the trie and reach a leaf that maximizes xor with Y (as described in your question), you can record two indices together with the maximum value (the index of Y is known as its the element you're about to add).

The equality f(l, r) = f(0, r) ^ f(0, l - 1) is proven here.

Once we have this equality and the solution to the first problem(with a slight modification described above to record the indices), we get the solution to the second problem immediately. How? We can compute f(i) for all valid i and then run this algorithm to get two indices that maximize xor. Let them be L and R, where L < R. Then the answer is the [L + 1, R] subarray.