In a normal scan, the upsweep part builds a list where the $i$th element is the sum of the $a_j$ elements betewen indices $i/2^k$ and $i$, where $k$ is the largest power of 2 such that $2^k \leqslant i$.
The downsweep part will then compute the prefix sums $p_i$ by summing some of the $ds_j$ values to the left of index $i$. Specifically, it will sum together the sums for $0\rightarrow i/2$, $i/2\rightarrow i/4,\ldots$, which are respectively at indices $i/2$, $i/2+i/4,\ldots$
This is done by pushing the partial sums down the array and adding them up with others so that they start at 0.
In the upsweep phase, the flag is used to mark final values (i.e. values that shouldn't be changed). When any sum is computed using a flagged value as its left-hand-side operand, it gets flagged as well. This ensures that there are no accesses beyond the start of any list.
In the downsweep phase, the flags now mark values that do not need to be added to when the partial sums are pushed down the list. At the beginning of this phase, this corresponds exactly to values that were flagged in the previous phase. The algorithm then proceeds as before, with the addition that the beginning of every sublist is simply cleared instead of being computed normally.
In a normal scan, the upsweep part builds a list where the $i$th element is the sum of the $a_j$ elements betewen indices $i/2^k$ and $i$, where $k$ is the largest power of 2 such that $2^k \leqslant i$.
The downsweep part will then compute the prefix sums $p_i$ by summing some of the $ds_j$ values to the left of index $i$. Specifically, it will sum together the sums for $0\rightarrow i/2$, $i/2\rightarrow i/4,\ldots$, which are respectively at indices $i/2$, $i/2+i/4,\ldots$
This is done by pushing the partial sums down the array and adding them up with others so that they start at 0.
In the upsweep phase, the flag is used to mark final values (i.e. values that shouldn't be changed). When any sum is computed using a flagged value as its left-hand-side operand, it gets flagged as well. This ensures that there are no accesses beyond the start of any list.
In the downsweep phase, the flags now mark values that do not need to be added to when the partial sums are pushed down the list. At the beginning of this phase, this corresponds exactly to values that were flagged in the previous phase. The algorithm then proceeds as before, with the addition that the beginning of every sublist is simply cleared instead of being computed normally.