The main idea behind the segmented scan here is to "flatten" the nested representation of the data into a single linear sequence, while storing metadata regarding the start of each original subsequence in order to allow for correct handling of the sequences independently. Once we have this flattened representation, we can run a slightly-modified version of the previously discussed parallel scan algorithm.
ishangaur
For some cases this also allows us to do less computation on data that we don't case about, like 0s in a matrix, while being able to actually get rid of them from our representation and reduce memory usage
The main idea behind the segmented scan here is to "flatten" the nested representation of the data into a single linear sequence, while storing metadata regarding the start of each original subsequence in order to allow for correct handling of the sequences independently. Once we have this flattened representation, we can run a slightly-modified version of the previously discussed parallel scan algorithm.