<p><em><a href="https://www.cs.cmu.edu/afs/cs/academic/class/15750-s11/www/handouts/PrefixSumBlelloch.pdf" rel="nofollow noreferrer">Prefix Sums and Their Applications</a></em> states that</p>
<blockquote>
<p>The all-prefix-sums operation takes a binary associative operator ⊕, and
an ordered set of n elements...</p>
</blockquote>
<p>Why is associativity a required property of the prefix sum operation? If a prefix sum is only ever calculated by scanning the set from left to right, why is associativity needed?</p>

CC BY-SA 4.0
2023-02-17T09:03:11.550Z
You don't need the associativity to define the problem but you need the associativity for the known efficient algorithms.
Louis
CC BY-SA 4.0
2023-02-17T13:01:34.423Z
The whole point of the article is how to compute the prefix sums efficiently *in parallel*. This most certainly won’t evaluate the operation by “scanning the set from left to right”. The particular sums will likely end up being evaluated as if they were bracketed in some sort of balanced binary tree whose exact shape will likely not be easy to define, and sums of different prefixes (even differing just by one element) will likely get evaluated by quite different trees, bearing no simple relationship to each other. Hence the result will be essentially useless for a non-associative operation.
Emil Jeřábek
CC BY-SA 4.0
2023-02-17T14:53:44.703Z
As @EmilJeřábek points out: prefix scan is a fundamental parallel computing primitive, and associativity lets you vary the evaluation order for performance.
Martin Berger
CC BY-SA 4.0
2023-02-17T19:41:53.260Z
Okay, my confusion was whether the associativity requirement was only for parallel/efficient implementations, or also for defining the general class of problems. I didn't see why associativity would be required for sequential/left-to-right scan implementations.
djlovesupr3me
<ds.algorithms>
Why does the prefix sum operation require its binary operator to be associative?
djlovesupr3me
# Why does the prefix sum operation require its binary operator to be associative?

(Asked by: username_0 on 2023-02-17)

*[Prefix Sums and Their Applications](https://www.cs.cmu.edu/afs/cs/academic/class/15750-s11/www/handouts/PrefixSumBlelloch.pdf)* states that

> The all-prefix-sums operation takes a binary associative operator ⊕, and
> an ordered set of n elements...

Why is associativity a required property of the prefix sum operation? If a prefix sum is only ever calculated by scanning the set from left to right, why is associativity needed?

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: You don't need the associativity to define the problem but you need the associativity for the known efficient algorithms.  
> **username_2**: The whole point of the article is how to compute the prefix sums efficiently *in parallel*. This most certainly won’t evaluate the operation by “scanning the set from left to right”. The particular sums will likely end up being evaluated as if they were bracketed in some sort of balanced binary tree whose exact shape will likely not be easy to define, and sums of different prefixes (even differing just by one element) will likely get evaluated by quite different trees, bearing no simple relationship to each other. Hence the result will be essentially useless for a non-associative operation.  
> **username_3**: As @EmilJeřábek points out: prefix scan is a fundamental parallel computing primitive, and associativity lets you vary the evaluation order for performance.  
> **username_0**: Okay, my confusion was whether the associativity requirement was only for parallel/efficient implementations, or also for defining the general class of problems. I didn't see why associativity would be required for sequential/left-to-right scan implementations.  

---

## 0 answers

