title: Find the subarray with the max XOR from an array (using a trie)
body: <p>The problem statement is:</p>
  
  <blockquote>
    <p>Given an array of integers, find the subarray with maximum XOR.</p>
  </blockquote>
  
  <p>Some examples are:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>I found a <a href="https://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems" rel="noreferrer">quora post</a> which provides an explanation of the solution to the problem but I'm not quite able to fully understand what is being explained.</p>
  
  <p>The post starts by introducing a similar problem to the one above (problem 1 in the post):</p>
  
  <blockquote>
    <p>Given an array of integers, we have to find two elements whose XOR is maximum</p>
  </blockquote>
  
  <p>It then describes a trie data structure which can handle two types of queries:</p>
  
  <blockquote>
    <ol>
    <li>Insert a number X</li>
    <li>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</li>
    </ol>
  </blockquote>
  
  <p><a href="https://i.stack.imgur.com/meqFv.png" rel="noreferrer"><img src="https://i.stack.imgur.com/meqFv.png" alt="enter image description here"></a>
  The above image handles query type 1. For query type 2, the post has the following:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>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:</p>
  
  <p><strong>e.g.</strong> 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. <strong>But how would the algorithm store which two elements have been xor to yield that max?</strong></p>
  
  <p>Finally, the logic from this approach is supposed to be applied to the problem (problem 2 in the post):</p>
  
  <blockquote>
    <p>Given an array of integers, find the subarray with maximum XOR</p>
  </blockquote>
  
  <p>Here, the following solution was provided:</p>
  
  <blockquote>
    <p>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&lt;=i. Suppose, we inserted F(1,L-1) in our trie for all L&lt;=i, then it's just problem 1.</p>
  </blockquote>
  
  <p>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, <strong>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?</strong> </p>
  
  <p>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.</p>