Find the maximum subarray XOR in a given array - GeeksforGeeks
https://www.cnblogs.com/1pha/p/8721373.html
另一种方法是“后缀数组+Trie字典树+贪心算法”。
后缀数组
定义preXori=A1xorA2xor...xorAipreXori=A1xorA2xor...xorAi，那么数组AA内任意子数组的异或和如下
resi,j=preXorixorpreXorj,i<=j
resi,j=preXorixorpreXorj,i<=j
因此，我们需要找到数组AA内所有的后缀子数组的异或和。然后，利用前面的数据，计算每个以AiAi结束的异或和的最大值。
Trie字典树
为了方便寻找合适的后缀数组异或和，利用Trie字典存储每个后缀数组异或和preXoripreXori。preXoripreXori以二进制（01）的形式存储到Trie中，因此该Trie也称为”01”字典树。从Trie的根往叶子节点的方向对应二进制preXoripreXori的高位到低位。例如preXori=(5)10=(101)2preXori=(5)10=(101)2，左数第一个1是高位，第二个1是低位。
该链接是一道Tire树的联系题：
http://blog.csdn.net/u010232171/article/details/43373697
贪心算法
完成上面两步后，开始计算以AiAi结束子数组的最大异或和。思路是用已知的preXori=A1xorA2...xorAipreXori=A1xorA2...xorAi作为Trie树的查询值。在查询过程中，力求找到与该值异或结果最大的值。遵循优先寻找对应二进制位上不同的节点（异或运算的特点1xor0=11xor0=1）。这样，高位趋近1，结果就是最大的。
https://shanzi.gitbooks.io/algorithm-notes/problem_solutions/max_xor_sub_sequence.html
https://github.com/cherryljr/NowCoder/blob/master/Find%20the%20Maximum%20Subarray%20XOR%20in%20an%20Array.java
https://www.geeksforgeeks.org/find-maximum-xor-value-sub-array-size-k/
Given an array of integers. find the maximum XOR subarray value in given array. Expected time complexity O(n).
Examples:
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
An Efficient Solution can solve the above problem in O(n) time under the assumption that integers take fixed number of bits to store. The idea is to use Trie Data Structure. Below is algorithm.
1) Create an empty Trie. Every node of Trie is going to
contain two children, for 0 and 1 value of bit.
2) Initialize pre_xor = 0 and insert into the Trie.
3) Initialize result = minus infinite
4) Traverse the given array and do following for every
array element arr[i].
a) pre_xor = pre_xor ^ arr[i]
pre_xor now contains xor of elements from
arr[0] to arr[i].
b) Query the maximum xor value ending with arr[i]
from Trie.
c) Update result if the value obtained in step
4.b is more than current value of result.
How does 4.b work?
We can observe from above algorithm that we build a Trie that contains XOR of all prefixes of given array. To find the maximum XOR subarray ending with arr[i], there may be two cases.
i) The prefix itself has the maximum XOR value ending with arr[i]. For example if i=2 in {8, 2, 1, 12}, then the maximum subarray xor ending with arr[2] is the whole prefix.
ii) We need to remove some prefix (ending at index from 0 to i-1). For example if i=3 in {8, 2, 1, 12}, then the maximum subarray xor ending with arr[3] starts with arr[1] and we need to remove arr[0].
We can observe from above algorithm that we build a Trie that contains XOR of all prefixes of given array. To find the maximum XOR subarray ending with arr[i], there may be two cases.
i) The prefix itself has the maximum XOR value ending with arr[i]. For example if i=2 in {8, 2, 1, 12}, then the maximum subarray xor ending with arr[2] is the whole prefix.
ii) We need to remove some prefix (ending at index from 0 to i-1). For example if i=3 in {8, 2, 1, 12}, then the maximum subarray xor ending with arr[3] starts with arr[1] and we need to remove arr[0].
To find the prefix to be removed, we find the entry in Trie that has maximum XOR value with current prefix. If we do XOR of such previous prefix with current prefix, we get the maximum XOR value ending with arr[i].
If there is no prefix to be removed (case i), then we return 0 (that’s why we inserted 0 in Trie).
If there is no prefix to be removed (case i), then we return 0 (that’s why we inserted 0 in Trie).
假设答案区间为 [L, R], 则答案为 XOR[L, R], 可以将区间分解为 XOR[L,R] == XOR[0, L - 1] ^ XOR[L, R],
因此
- 不断更新所以数字的 前缀异或和, 将每一个前缀异或和 都 保存到 01Trie 中
- 在 01Trie 中查询与它 异或值最大 的 前缀异或和
- 根据 Step2 的结果, 更新 ans. 重复第一步, 直至无剩余元素.
需要注意的是, 对于样例中的 3 8 2 6 4 的 前缀异或和分别 为 3 11 9 15 11, 最大值为15, 区间为 [0, 4), 因此每个Trie的初始状态应存在 0.
struct BinTrie {
BinTrie* next[2];
BinTrie() {
next[0] = next[1] = NULL;
}
};
void insertNum(BinTrie* root, unsigned num) {
BinTrie* p = root;
for(int i = 31; i >= 0; i--) {
int index = (num >> i) & 1;
if(!p->next[index])
p->next[index] = new BinTrie();
p = p->next[index];
}
}
unsigned queryDiff(BinTrie* root, unsigned num) {
num = ~num;
BinTrie* p = root;
unsigned ret = 0;
for(int i = 31; i >= 0; i--) {
int index = (num >> i) & 1;
if(!p->next[index])
index = 1 - index;
ret += (index << i);
p = p->next[index];
}
return ret;
}
int main() {
int nTest; scanf("%d", &nTest);
while(nTest--) {
int nNum; scanf("%d", &nNum);
unsigned pre = 0, ans = 0;
BinTrie* root = new BinTrie();
// 保证了 [0, x) 区间的合理性
// 否则对于 15 来说, Trie中最大不同的前缀异或和 queryDiff(root, pre) 并不为 0
insertNum(root, 0);
while(nNum--) {
unsigned num; scanf("%u", &num);
pre = pre ^ num;
insertNum(root, pre);
ans = max(ans, queryDiff(root, pre) ^ pre);
}
printf("%u\n", ans);
}
return 0;
}
https://blog.csdn.net/u010232171/article/details/49685523另一种方法是“后缀数组+Trie字典树+贪心算法”。
后缀数组
定义preXori=A1xorA2xor...xorAipreXori=A1xorA2xor...xorAi，那么数组AA内任意子数组的异或和如下
resi,j=preXorixorpreXorj,i<=j
resi,j=preXorixorpreXorj,i<=j
因此，我们需要找到数组AA内所有的后缀子数组的异或和。然后，利用前面的数据，计算每个以AiAi结束的异或和的最大值。
Trie字典树
为了方便寻找合适的后缀数组异或和，利用Trie字典存储每个后缀数组异或和preXoripreXori。preXoripreXori以二进制（01）的形式存储到Trie中，因此该Trie也称为”01”字典树。从Trie的根往叶子节点的方向对应二进制preXoripreXori的高位到低位。例如preXori=(5)10=(101)2preXori=(5)10=(101)2，左数第一个1是高位，第二个1是低位。
该链接是一道Tire树的联系题：
http://blog.csdn.net/u010232171/article/details/43373697
贪心算法
完成上面两步后，开始计算以AiAi结束子数组的最大异或和。思路是用已知的preXori=A1xorA2...xorAipreXori=A1xorA2...xorAi作为Trie树的查询值。在查询过程中，力求找到与该值异或结果最大的值。遵循优先寻找对应二进制位上不同的节点（异或运算的特点1xor0=11xor0=1）。这样，高位趋近1，结果就是最大的。
https://shanzi.gitbooks.io/algorithm-notes/problem_solutions/max_xor_sub_sequence.html
https://github.com/cherryljr/NowCoder/blob/master/Find%20the%20Maximum%20Subarray%20XOR%20in%20an%20Array.java
* Approach: Trie 对于 Subarray 问题，我们可以考虑 PreSum, Two Pointer, DP 等方法，
* 经过分析，我们发现也就只有 PreXOR(EOR) 的方法可以用一用。 总体思路为：求所有以 i 作为结尾的 最大异或 子数组。那么答案必定在这里面。
* 但是我们发现在本题中无法利用 HashMap 实现加速。（因为我们没办法通过它来求得 最大异或和）
* 因此我们需要考虑另外的一种数据机构来帮我们实现加速。而这里使用的就是 Trie Tree.
*
* 我们在 Trie Tree 中放入了放入了 从0到i 的异或值 EOR. 那么根据 异或运算 的性质： A^B=C => B^C=A 我们可以通过
* 0...i 的异或和计算出 任意 j...i 的异或值： XOR[j...i] = XOR[0...i] ^ XOR[0...j-1]
*
* 那么Trie如何实现快速得到 异或后的最大值 呢？（本题的核心部分） 我们是按照这样的策略（其实是一个贪心的做法）： 对于一个 int 类型，总共有 32
* 位。因此我们 Trie Tree 的高度为 32. 当我们想要查询如何获得最大的异或值时， 我们可以 从高位开始 向低位逐位查找 最佳异或值。遵循着
* 首先满足高位 的做法依次向下查询。 同时：我们还需要注意符号位，这里比较特殊，因为 0 代表正，1代表负。 所以对于 符号位 我们要取与原来位置上 相同
* 的数， 而对于其他位我们要去与原来位置上 不同的数（异或1后的数）。 如果 取不到 最佳值的话，我们就只能取现有的值了（总共就两个...）
* 最后假设我们得到的 最大异或和 为：EOR[x]^EOR[y]，那么就说明 最大异或和子数组为：[x+1...y] 这样查找下来我们需要循环 32
* 次，时间复杂度为 O(1) 而我们需要查找 n 个数，因此总体时间复杂度为 O(n)
*/
public int maxSubarrayXOR(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
Trie trie = new Trie();
// 初始化 trie，将 0 将入到 trie 中，因为 X^0=X
trie.add(0);
int eor = 0;
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
eor ^= nums[i];
// 在 Trie 中寻找与 eor 异或起来最大的元素，返回异或之后的结果
max = Math.max(max, trie.maxXOR(eor));
// 将 eor 加入到 Trie Tree 中
trie.add(eor);
}
return max;
}
class TrieNode {
// Trie Tree 的节点，因为是 2进制，所以我们只需要 0,1 两个节点即可
TrieNode[] child;
TrieNode() {
child = new TrieNode[2];
}
}
class Trie {
TrieNode root;
Trie() {
root = new TrieNode();
}
// 将 nums[i] 加入到 Trie Tree 中
public void add(int num) {
TrieNode curr = root;
for (int i = 31; i >= 0; i--) {
int path = ((num >> i) & 1); // 获得第 i 位上的值
if (curr.child[path] == null) {
curr.child[path] = new TrieNode();
}
curr = curr.child[path];
}
}
public int maxXOR(int num) {
TrieNode curr = root;
int rst = 0;
for (int i = 31; i >= 0; i--) {
// 获得第 i 位上的值
int path = ((num >> i) & 1);
// 根据 path，我们需要得到相应的最佳 异或值
// 注意：如果是 符号位 的话，我们取与path相同的值，否则取与 path 不同的值
int best = i == 31 ? path : (path ^ 1);
// 判断 curr.child[best] 节点是否存在，存在的话我们就能取到最佳值
// 否则只能取另外一个值了
best = curr.child[best] != null ? best : (best ^ 1);
// 将 rst 的第 i 位置为 path^best
rst |= ((path ^ best) << i);
curr = curr.child[best];
}
return rst;
}
}
https://www.quora.com/How-do-I-find-a-subarray-with-maximum-xor
A Simple Solution is to use two loops to find XOR of all subarrays and return the maximum.
int maxSubarrayXOR(int arr[], int n){ int ans = INT_MIN; // Initialize result // Pick starting points of subarrays for (int i=0; i<n; i++) { int curr_xor = 0; // to store xor of current subarray // Pick ending points of subarrays starting with i for (int j=i; j<n; j++) { curr_xor = curr_xor ^ arr[j]; ans = max(ans, curr_xor); } } return ans;}https://www.geeksforgeeks.org/find-maximum-xor-value-sub-array-size-k/
Given an array of integers, the task is to find maximum XOR value of a subarray of size K.
Examples :
Input : arr[] = {2, 5, 8 ,1 , 1 ,3} k = 3
Output : 15
Explanation : All subrrays of size k (=3) and
their XOR values are:
{2, 5, 8} => XOR value = 15
{5, 8, 1} => XOR value = 12
{8, 1, 1} => XOR value = 8
{1, 1, 3} => XOR value = 3
Maximum of all XOR values = 15
An efficient solution takes O(n) time. The idea is simple, we can find XOR value of current subarray of size k by removing first element of previous subarray and adding last element of current subarray. We can remove an element from current XOR by doing XOR of it again because of property of XOR that a ^ x ^ x = a.
