### PROBLEM LINK:

**Author:** Zi Song Yeoh

### DIFFICULTY:

EASY-MEDIUM

### PREREQUISITES:

BINARY SEARCH, TRIES, SEGMENT TREES

### PROBLEM:

Given Q queries (l, r, x), find the maximum value of a_{j} \otimes x where l \le j \le r.

### EXPLANATION:

The first subtask is trivial : You can just iterate through all elements in range for each query to find the answer.

The third subtask has x = 0, which reduces the problem to Range Maximum Query, which can be solved with Sparse Table or Segment Trees in O(n\log n).

Now, letâ€™s see how to solve the second subtask. One way to solve this is by building a trie (though itâ€™s not neccesary and the same solution can be applied to the sorted array of numbers instead). Build a trie for all the numbers in range [l, r]. We walk down the trie from the root. Whenever we have a choice of whether to go left or right, we pick the choice that maximizes the final xor value, i.e. if the current bit of x is 0, choose the path that is labelled 1 and vice versa. Thus, each query can now be solved in O(\log n) time.

We can generalize this idea to solve the whole problem. What we need here is a segment tree of tries (or segment tree of sorted arrays is sufficient in this case). We can build a trie for each segment of the segment tree in O(n\log n\log a_{i}) time and for each query, we need to query the trie in O(\log n) segments. Thus, the whole solution would work in O((n + q)\log n\log a_{i}) time.

### AUTHORâ€™S AND TESTERâ€™S SOLUTIONS:

Authorâ€™s solution can be found here.

Testerâ€™s solution can be found here.