Folding many into one
A reduction combines many values into one using a binary operator, like summing an array. Done sequentially it walks every element one at a time, taking work proportional to the input size and the same number of steps.
Building the tree
If the operator is associative, the order of combining does not change the result. That freedom lets us pair up neighbors and combine them at the same time:
- In the first round, combine elements in pairs, halving the count.
- In the next round, combine the surviving partial results in pairs again.
- Repeat until a single value remains.
Because each round halves the number of values, the number of rounds is logarithmic in the input size, even though the total amount of work stays the same.
Why associativity matters
The operator must be associative so that regrouping is safe. Commutativity is not required because each combine still keeps left and right operands in order. Floating point addition is not perfectly associative, so parallel sums can differ slightly from sequential ones.
Key idea
A reduce tree exploits associativity to combine values in pairs each round, shrinking a long fold from linear depth to logarithmic depth while keeping total work the same.