I just used 2 observations to solve this problem.
- All X_0 values at a certain depth appear xor-ed together at their ancestors X value or not at all. So all X_0 values at the same depth can be xor-ed together to convert the tree to a chain. I see your approach also uses this.
- If the length of the resulting chain is d, then the number of operations after which it reverts to its initial form, i.e its period, is the nearest power of 2 \ge d. Also the pattern of inclusion of values at the root xor-sum is recursive… this is what I mean. If split into two halves, each term either repeats the pattern of the left half as the right half, or leaves the right half empty.
So we can make up the chain to the nearest power of 2 by padding with zeroes for convenience, and then the pattern can be generated by splitting the chain into two halves, solving recursively, and combining (similar to mergesort). Here is my solution, although I have used an iterative version instead of recursion. The complexity is \mathcal{O}(N \log N).
EDIT (The merging and solving procedure in greater detail):
Suppose A is the chain derived from the tree with length d, which is a power of 2. Take a look at the pseudocode below, the terms should be self-explanatory.
function solve(A, L, R): N = R - L + 1 if N equals 1: return solve(A, L, L+N/2-1) solve(A, L+N/2, R) A_L = slice of A from L to L+N/2-1 A_R = slice of A from L+N/2 to R for i in [0..N/2-1]: A[L+i] = A_L[i] xor A_R[i] A[L+N/2+i] = A_L[i]
Calling solve(A, 0, d-1)
will compute all d possible answers in A. The algorithms works by recursively computing the same sequence of the pattern of inclusion in both the halves of size N/2
each. Then it generates the current pattern sequence of size N
by either incorporating both the left and right value or just the left value, in the proper order of course.
For example, if N = 8
, the pattern and the half pattern is
11111111 1111 10101010 1010 11001100 1100 10001000 1000 11110000 10100000 11000000 10000000
So A_L
and A_R
will be
-- A_L --|-- A_R -- A_L[0] = A[L] ^ A[L+1] ^ A[L+2] ^ A[L+3] | A_R[0] = A[L+4] ^ A[L+5] ^ A[L+6] ^ A[L+7] A_L[1] = A[L] ^ A[L+2] | A_R[1] = A[L+4] ^ A[L+6] A_L[2] = A[L] ^ A[L+1] | A_R[2] = A[L+4] ^ A[L+5] A_L[3] = A[L] | A_R[3] = A[L+4]
And then they will be combined into
A[L] = A_L[0] ^ A_R[0] = A[L] ^ A[L+1] ^ A[L+2] ^ A[L+3] ^ A[L+4] ^ A[L+5] ^ A[L+6] ^ A[L+7]
A[L+1] = A_L[1] ^ A_R[1] = A[L] ^ A[L+2] ^ A[L+4] ^ A[L+6]
A[L+2] = A_L[2] ^ A_R[2] = A[L] ^ A[L+1] ^ A[L+4] ^ A[L+5]
A[L+3] = A_L[3] ^ A_R[3] = A[L] ^ A[L+4]
A[L+4] = A_L[0] = A[L] ^ A[L+1] ^ A[L+2] ^ A[L+3]
A[L+5] = A_L[1] = A[L] ^ A[L+2]
A[L+6] = A_L[2] = A[L] ^ A[L+1]
A[L+7] = A_L[3] = A[L]
That took some typing… hope it’s clearer now
Also I hadn’t noticed this before, but I now recognize the pattern as the Sierpinski triangle. Awesome!