Max XOR of a subarray in O(n)

Правка en1, от TunaMayoSandwich, 2023-12-17 13:25:25

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;
}
Теги bitmask, xor, arrays

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en15 Английский TunaMayoSandwich 2024-07-27 20:02:31 5 Tiny change: 'leq l_{i} < i-1$ one ' -> 'leq l_{i} \leq i-1$ one '
en14 Английский TunaMayoSandwich 2024-07-27 19:55:49 49 Tiny change: ' f(l, r) \rightarrow f(0, r) \' -> ' f(l, r) \implies f(0, r) \'
en13 Английский TunaMayoSandwich 2024-07-26 21:58:08 66 Tiny change: 'eq m$, $0 leq l_{i} ' -> 'eq m$, $0 \leq l_{i} ' (published)
en12 Английский TunaMayoSandwich 2024-07-26 21:43:15 42
en11 Английский TunaMayoSandwich 2024-07-26 21:29:33 675 Tiny change: 'barray in O(nlogC) as it per' -> 'barray in $O(n \cdot logC)$ as it per' (saved to drafts)
en10 Английский TunaMayoSandwich 2024-01-01 03:59:17 2 Tiny change: ' all 0 <= I <= n-1. T' -> ' all 0 <= i <= n-1. T'
en9 Английский TunaMayoSandwich 2023-12-18 23:27:31 2 Tiny change: 'y case, than the vamp' -> 'y case, then the vamp'
en8 Английский TunaMayoSandwich 2023-12-18 20:31:13 2 Tiny change: 'of **a** form index l ' -> 'of **a** from index l '
en7 Английский TunaMayoSandwich 2023-12-17 23:01:47 2 Tiny change: 'st value it the array' -> 'st value in the array'
en6 Английский TunaMayoSandwich 2023-12-17 16:54:31 23 Tiny change: 'having expended it to' -> 'having expanded it to'
en5 Английский TunaMayoSandwich 2023-12-17 14:52:49 4 Tiny change: 'ray in O(n) as it pe' -> 'ray in O(nlogC) as it pe'
en4 Английский TunaMayoSandwich 2023-12-17 14:51:42 51
en3 Английский TunaMayoSandwich 2023-12-17 14:16:27 0 (published)
en2 Английский TunaMayoSandwich 2023-12-17 14:09:12 8183 Tiny change: 'ains to this problem [' -> 'ains to the problem ['
en1 Английский TunaMayoSandwich 2023-12-17 13:25:25 2842 Initial revision (saved to drafts)