This block is still quite complicated. Let's say you have partitioned frequency sequence
~~~
1 2 1 3 || 1 1 1 1 || 1 2 3 2
~~~
From left to right, you want
~~~
1 3 4 7 || 8 9 10 11 || 12 14 17 19
~~~
From right to left, you want
~~~
19 18 16 15 || 12 11 10 9 || 8 7 5 2
~~~
This can be done by first computing partition-wise sums:
~~~
7 || 4 || 8
~~~
Then compute cumsums from left to right
~~~
0 || 7 || 11 || 19
~~~
and from right to left
~~~
19 || 12 || 8 || 0
~~~
The global cumsum becomes, from left to right
~~~
0 + cumsum(1, 2, 1, 3) || 7 + cumsum(1, 1, 1, 1) || 11 + cumsum(1, 2, 3, 2)
~~~
from right to left
~~~
19 - cumsum(0, 1, 2, 1) || 12 - cumsum(0, 1, 1, 1) || 8 - cumsum(0, 1, 2, 3)
~~~
There are some details I may miss. But two jobs should be sufficient for this computation.