Let $T$ be a rooted, finitely branching tree, with values from $A$ in its nodes; $T(j)$ is the value of a node called $j$. $A$ is a commutative monoid. The "bottom-up scan tree" of $T$ is a rooted tree $T^\ast$ isomorphic to $T$, such that if $j$ is a leaf of $T$, $T(j)=T^\ast(j)$, and otherwise $T^\ast(j) = \sum_{i\leq j}T(i)$, where $i\leq j$ indicates that $i$ is a descendant of $j$.

What algorithms exist to compute $T^\ast$ quickly on a parallel random access machine?

In the real world, how should $T^\ast$ and $T$ be implemented in order to get good performance on a GPU?

My motivation comes from studying the description of the network simplex algorithm in the book "Network flows" by Ahuja and Magnanti, where this problem appears as "compute-flows" in section 11.4. I am trying to solve optimal transport problems.

I think that it should be relatively straightforward to solve this problem in a loop indexed by the height of tree, where the time of each loop iteration is at most $\log(N)$. If the tree is balanced, then this algorithm suffices, and there is no need for sophisticated algorithms. However, I can see no reason why the trees in the network simplex algorithm for minimum flow cost should be reasonably balanced. (If there are adaptations of the network simplex algorithm where the tree is always balanced, I would be interested in hearing about this.)