Finger tree allowing apply functions to each element
Let be a monoid. We are interested in maintaining a sequence under all updates currently supported by finger tree. However, we are also interested in adding another update, which we call the function update.
The functions satisfies the following property.
The sequence is given implicitly, where it has two methods:
evaluate(X): It returns for any sequence such that .
split(j): returns a representation for and .
We are interested in implementing
FunctionUpdate(a,f), the output would be a representation of the sequence .
Many problems actually require update to a entire interval of the sequence, which makes this extremely valuable. For example, consider the following simple problem.
Maintain a sequence of integers , such that we can do the operation , which increment all numbers from th to th index by . That is, the new sequence is . Also, it has a function which returns . This problem can be solved by finger tree with function update operation.
I want an actual implementation of such data structure so I can implement the min-cost flow algorithm for series-parallel graphs .
 H. Booth, R.E. Tarjan, Finding the minimum-cost maximum flow in a series-parallel network, Journal of Algorithms. 15 (1993) 416–446 10.1006/jagm.1993.1048.