Calculate an associative function, f, on all prefixes of an n-element array, that is, s(0), f(s(0), s(1)), f(s(0), f(s(1), s(2))), ..., f(s(0), f(s(1), ... f(s(n-2), s(n-1))...)), using Θ(n) processors in Θ(log n) time. The algorithm is

 for j := 0 to lg(n)-1 do 
 for i := 2j to n-1 parallel-do
 s(i) := f(s(i-2j), s(i)) 

where lg is the logarithm base 2, and parallel-do does the innermost computations in parallel.