I did not quite get the idea of the second stages. What is the intuition behind that?

+1 to Nian's question - I'm also a bit confused by this. Perhaps it would be helpful to have some prose for this slide (and similar slides) describing what is happening in each line and what the arrows mean so it's easier to review after lecture.

Adding to the comments above, with "simply encountered problems" like the ones above, can we expect that solving problems with the CUDA language would require a lot of this type of thinking? (because it seems to me that these problems require a lot of work and design which isn't always intuitive to come with)

I believe that the intuition behind the second stage here is that at the end of the first stage we have a few sums over disjoint regions which we would like to combine, so we perform a sequence of swaps in order to move these sums next to each other. For example, at the end of the first stage we have a_{12-13} and a_{10-11}. These are combined together to form a_{10_13} on the third line in the second stage. There is a bit more than just this going on, but it seems like at a high level the first stage simply accumulates sums over larger and larger regions whereas the second stage performs pairwise swaps in order to move some of the sums to locations where they can be used to compute new sums in their final location.