I'm not sure I completely understand the correctness of this algorithm. The upsweep finishes with each index having the value of the last sum from a left branch there. The downsweep combines and swaps elements at smaller and smaller strides. I feel like this is a way that could be explained by adding up digits in the binary representation, but that metaphor does not completely map to this algorithm.
I'm not sure I completely understand the correctness of this algorithm. The upsweep finishes with each index having the value of the last sum from a left branch there. The downsweep combines and swaps elements at smaller and smaller strides. I feel like this is a way that could be explained by adding up digits in the binary representation, but that metaphor does not completely map to this algorithm.