984. The Best XOR of a Contiguous Stretch
Given n values, print the largest XOR of a contiguous stretch of them. A
stretch is one or more values next to each other, and its XOR is all of them
combined with XOR.
1 2 3 4 -> 7 the stretch 3 4
7 -> 7
0 0 0 -> 0
8 1 2 12 -> 15 the stretch 1 2 12
1 2 4 8 16 -> 31 the whole array
## Two ideas that are each already in the bank
Trying every stretch is n (n - 1) / 2 of them, which at n = 100000 is
4999950000, about five billion, even with the running XOR making each one cost a
single operation.
Problem 731 turns range XOR into a pair of prefix values. With
P[0] = 0, P[i] = a[1] XOR a[2] XOR ... XOR a[i]
the XOR of the stretch from l to r is P[r] XOR P[l-1], because everything
before l appears in both terms and cancels itself out. XOR is its own inverse,
so there is no subtraction to get wrong.
Problem 976 finds the largest XOR of a pair from a set, in O(30 n), with a
binary trie.
Put them together: the answer is the largest XOR of two DIFFERENT entries of the
array P[0] .. P[n].
## The sweep
insert 0 into the trie # this is P[0]
pref = 0, best = 0
for each value x:
pref = pref xor x
best = max(best, bestXorAgainstTrie(pref))
insert pref
print best
## Why P[0] = 0 must be in the trie
A stretch starting at the very first position uses P[0], and P[0] is 0
because the empty prefix combines nothing. Leaving it out loses exactly the
stretches that begin at position 1, and on 1 2 4 8 16 that loses the whole
array, which is the answer. The seed is not a convention, it is the term that
makes l = 1 expressible.
This is the same seeding rule as problems 731 and 733, and it is the most common error in the prefix family.
## Why every stretch is considered exactly once
Each pair (l, r) with 1 <= l <= r <= n corresponds to the pair of prefix
indices (l-1, r), which are different because l - 1 < r. That map is a
bijection between stretches and pairs of different prefix indices, so maximising
over one is maximising over the other. The sweep above queries each P[r]
against every earlier P[i], which covers every such pair once, exactly as
problem 976 does.
## The answer is never negative and the empty stretch is excluded
best starts at 0, which is legitimate: a single value of 0 makes the answer 0,
and the all-zero array answers 0. Nothing here needs a "no stretch found"
sentinel, because n is at least 1 and a single value is a stretch.
## Overflow
Nothing here overflows. Every value and every prefix XOR stays below
2^30 = 1073741824, because XOR never produces a value larger than its largest
operand. That is worth noticing: a prefix SUM grows without bound and a prefix
XOR does not, so the usual 64 bit caution for prefix arrays is unnecessary here.
## Cost
Time O(30 n), one insertion and one query per position. Space is at most
1 + 30 (n + 1) = 3000031 nodes.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ each value ≤ 1073741823`, which is `2^30 - 1`
Input
The first line contains an integer n.
The second line contains n integers.
Output
Print one integer: the largest XOR obtainable from one contiguous stretch of one or more of the values.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.