Recursive Sequence Tree Problem (Original Research in the Field of Comp. Sci) This question appears also in https://cstheory.stackexchange.com/questions/17953/recursive-sequence-tree-problem-original-research-in-the-field-of-comp-sci. I was told that cross-posting in this particular situation could be approved, since the question can be viewed from many angles.
I am a researcher in the field of computer science. In my research I have the following problem, which I have been thinking for quite a while now. 
I think the problem is best explained through an example, so first assume this kind of a tree structure:

                 1, 2, 3, 4, 5, 6, 7, 8
                /                      \
    6, 8, 10, 12                       -4, -4, -4, -4
   /            \                      /             \ 
 16, 20       -4, -4                -8, -8,         0, 0
 /    \       /    \                /     \        /    \
36    -4    -8      0             -16      0      0      0

The root of the tree is always some sequence $s = (s_0, ..., s_{N-1})$ where $N = 2^p$ for some $p \in \mathbb{N}, p>2$.  Please note that I am looking for a general solution to this, not just for sequences of the form $1, 2, ..., 2^p$. As you can see, the tree is defined in a recursive manner: the left node is given by $left(k)=root(k)+root(\frac{N}{2}+k), \quad 0 \leq k \leq \frac{N}{2}$ 
and the right node by
$right(k)=root(k)-root(\frac{N}{2}+k), \quad 0 \leq k \leq \frac{N}{2}$ 
So, for example, (6 = 1+5, 8 = 2+6, 10 = 3+7, 12 = 4+8) and (-4 = 1-5, -4 = 2-6, -4 = 3-7, -4 = 4-7) would give the second level of the tree.
I am only interested in the lowest level of the tree, i.e., the sequence (36, -4, -8, 0, -16, 0, 0, 0). If I compute the tree recursively, the computational complexity will be $O(N log N)$. That is a little slow for the purpose of the algorithm. Is it possible to calculate the last level in linear time?
If a linear-time algorithm is possible, and you find it, I will add you as an author to the paper the algorithm will appear in. The problem constitutes about 1/10 of the idea/content in the paper. 
If a linear-time algorithm is not possible, I will probably need to reconsider other parts of the paper, and leave this out entirely. In such a case I can still acknowledge your efforts in the acknowledgements. (Or, if the solution is a contribution from many people, I could credit the whole math SE community.)

This is more of a comment, but it's too big for the comment block.  An interesting note on Kaya's matrix $\mathbf{M}$: I believe that it can be defined recursively for any value of $p$.  (I should note here that this is my belief.  I have yet to prove it...)
That is, let $\mathbf{M}_p$ be the matrix for the value of $p$ (here, let's remove the bound on $p\gt2$).  
Let $\mathbf{M}_1 = \begin{pmatrix}1 & 1 \\ 1 & -1\end{pmatrix}$.
Then $\mathbf{M}_n = \begin{pmatrix} \mathbf{M}_{n-1} & \mathbf{M}_{n-1} \\ \mathbf{M}_{n-1} & -\mathbf{M}_{n-1}\end{pmatrix}$.
Ah Ha!  Thanks to some searches based off of Suresh Venkat's answer, I found that this matrix is called the Walsh Matrix.  Multiplying this matrix by a column vector of your first sequence provides a column vector of the bottom sequence.
As a side note, this makes an almost fractal-like pattern when colored. :)

The above is for $p=4$.
EDIT: I'm almost sure I've seen a graphic similar to the one above before.  If someone recognizes something similar, that would be great...
