Lesson 24: Parallel Scan (Prefix Sum) — the Idea
A scan, or prefix sum, turns an array into the sequence of its running totals. In an inclusive scan the output at position i is the sum of all elements from 0 to i inclusive: output[i] = in[0] + in[1] + ... + in[i]. For example [3,1,2,4] becomes [3,4,6,10]. There is also an exclusive variant that st
Imagine a row of people, each holding a number. You want each, in the end, to hold the sum of themselves and everyone standing before them. The slow way: each whispers to the next neighbor, one after another. The fast way: in the first round each adds to themselves the number of whoever stands one step to their left. Next round — whoever is two steps left. Then four. The jumps double, and it finishes in just a few rounds.
- prefix sum / scan
- Turning an array into its running totals. In an inclusive scan, output[i] is the sum of in[0..i] inclusive.
- inclusive vs exclusive
- Inclusive: each output includes the element at its position ([3,1,2,4]->[3,4,6,10]). Exclusive: starts at zero and shifts right ([0,3,4,6]).
- the doubling idea
- Each round every element adds the neighbor d away, and d doubles (1,2,4,...). After log2(n) rounds each position has accumulated all predecessors.
- running total
- The sum accumulated up to a given point. The sequential version computes it in one loop in O(n) steps.
