979. The Best XOR So Far
You are given n values. For every position from the second onwards, print the
largest XOR of the value at that position with any value BEFORE it.
Print the n - 1 answers on one line, separated by single spaces.
3 10 5 25 2 8 -> 9 15 28 27 17
0 1073741823 -> 1073741823
7 7 7 7 -> 0 0 0
1 2 4 8 16 -> 3 6 12 24
Check the third answer of the first line. The value is 25 and the earlier values are 3, 10 and 5, giving 26, 19 and 28, so 28.
## Problem 976 prints the maximum of these numbers
976 asks only for the largest over the whole array, so it can throw each answer
away after comparing. Here every one of them is output, which removes the one
shortcut that hides a bug: an implementation that inserts the current value
before querying gets 0 for every position in 976 only when the true answer is
also 0, and gets 0 for every position here always.
## The sweep
insert a[0]
for i from 1 to n-1:
print bestXorAgainstTrie(a[i]) # the walk of problem 973
insert a[i]
Query first, then insert. The order is the whole problem.
## Why the answers are correct and the order is forced
When position i is queried, the trie holds exactly a[0] .. a[i-1], which is
the set the question asks about. Inserting a[i] first would add a[i] to that
set, and a[i] XOR a[i] is 0, which never beats anything, so the printed maximum
would be unchanged UNLESS every earlier pair is also 0. That is why the bug is
invisible on most inputs and produces 0 0 0 on the all-equal case, which is
also the correct answer there, so even that does not catch it. The case that
catches it is a repeated value followed by a different one.
## The first position
There is nothing before position 1, so no answer is printed for it and the output
has n - 1 numbers rather than n. The statement guarantees n is at least 2,
so there is always at least one number to print.
## Overflow
Nothing here overflows. Values and answers are below 2^30 = 1073741824, inside
the 2147483647 limit of a signed 32 bit integer.
## Cost
Time O(30 n), one query and one insertion per position. Space is at most
1 + 30 n = 3000001 nodes.
Constraints - `2 ≤ n ≤ 100000` - `0 ≤ each value ≤ 1073741823`, which is `2^30 - 1` - Values may repeat.
Input
The first line contains an integer n.
The second line contains n integers.
Output
Print n - 1 integers on a single line, separated by single spaces: for each position from the second to the last, the largest XOR of that value with any value at an earlier position.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.