Principe : y0 = x0, y1 = x0 + x1; y2 = x2 + x1 + x0, etc

Applications : Radix sort • Quicksort • String comparison • Lexical analysis • Stream compaction • Polynomial evaluation • Solving recurrences • Tree operations • Histograms,

Implémentation work-efficient :

y[0] = x[0];
for (i = 1; i < Max_i; i++)
    y[i] = y [i-1] + x[i];

Complexité : linéaire O(N)