Is each one of these operations done in-place? Otherwise, I think each step we need to do O(N) work which would not give us O(N) work overall.

I also don't quite understand where the 15th element went in the second half of the slide:(

For the second question, it was mentioned two slides after this that this is doing an exclusive scan so we can throw away the last element.

Just wanted to point out that this reminds me greatly of merge sort -- I wonder if we can apply the optimized algorithms we have in other domains to parallelize these functions as well!

thread17 For the first question, I think you are right. we are doing those operations in-place since we do not need the original value, and just need to keep a partial sum. (we don't need $a_3$, but $a_{2-3}$ and $a_{0-3}$ for example)

O(N) is derived from the geometric sum: N+N/2+N/4+...

How does one even come up with an algorithm like this? It doesn't really seem super intuitive...

@tp that was my question as well...

I think this came up 40 years ago: https://dl.acm.org/doi/10.1145/322217.322232

@suninhouse Same with me... Can't imagine how someone could come up with this genius method such a long time ago.

It looks like if we are doing an inclusive scan, we don't need the second stage. We just need to add the a_{0-7} and a_{8-15} together at the end of the first stage.

I want to remove my last comment now. I just realized scan is different from reduce.