As a pupil who has started training intensely not too long ago there are a lot of problems I come across that I can't figure out by myself, at least not in a contest's time. Most of the time there are great resources available online and on this very site to learn more and understand all the nuances implied in these problems, but I recently came across what is regarded as a "standard problem" and couldn't find satisfying explanations about it so I decided to write one myself hoping it'll be of some help to other beginners. I am going to discuss the problem of finding the maximum bitwise XOR of a subarray in O(n) as it pertains to this problem 1847C - Vampiric Powers, anyone?. I'll try to be as formal as possible and only skip over basic concepts (what is a subarray, what is bitwise xor, etc).

Task

Given an array a, let's define f(l, r) = xor of elements of a form index l to r, where 0 <= l < r <= n-1. Find max f(l,r) in O(n).

Solution

The idea is to use the fact that f(0, r) = f(0, l-1) ^ f(l, r) -> f(0, r) ^ f(0, l-1) = f(l, r). This means that one can traverse the array and maintain a variable pre_xor = f(0, i) where I is the current position, then all that remains is to find l-1 such that pre_xor ^ f(0, l-1) is maximised, this way one has found max (f(0, i) ^ f(0, l-1)) = max f(l, i) and solves the problem by iterating over all values of I from left to right.

The ideal way to find l-1 is to create a trie data structure. A trie is a k-ary search tree but in this case a branch is going to represent a bit and a path a umber, since bits can only be 1s and 0s the trie will simply be a standard binary tree.

struct trieNode{
	ll value;
	trieNode *arr[2];
};

trieNode *newNode(){
	trieNode *temp = new trieNode;
	temp->value = 0;
	temp->arr[0] = NULL;
	temp->arr[1] = NULL;
	return temp;
}

Start traversing a from index 0 and insert pre_xor into the trie. To insert a number in the trie take a look at its bits from the most significant downwards, if it's set to 1 take a step right, otherwise take a step left and create new nodes along the way if needed. Exciting this cycle a path'll have been created through the trie representing pre_xor. Append pre_xor to the end of this path so that when one reaches a leaf he has a convenient way of knowing what number he has arrived to. Note that nowhere in a trie node 1s and 0s appear, one just has to decide on a convention (right = 1, left = 0) and the encoding of 1s and 0s becomes implicit.

void insert(trieNode *root, ll pre_xor, ll max_bits){
	trieNode *temp = root;
 
	bool val;
	for (ll i=max_bits; i>=0; i--){
		val = pre_xor & (1<<i);
 
		if (temp->arr[val] == NULL) temp->arr[val] = newNode();
		temp = temp->arr[val];
	}
 
	temp->value = pre_xor;
}