The main point is that the operator is a
side-effect-free, associative function
This means that
(a op b) op c == a op (b op c)
Therefore, if you split the array into two halves and apply the parallelPrefix method recursively on each half, you can later merge the partial results by applying the operation on each element of the second half of the array with the last element of the first half.
Consider the [2, 1, 0, 3] with addition example. If you split the array into two halves and perform the operation on each half, you get:
[2, 3] and [0, 3]
Then, in order to merge them, you add 3 (the last element of the first half) to each element of the second half, and get:
[2, 3, 3, 6]
EDIT: This answer suggests one way of computing the prefixes of an array in parallel. It’s not necessarily the most efficient way, and not necessarily the way used by the JDK implementation. You can further read about parallel algorithms for solving that problem here.