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.
Let .
The functions satisfies the following property.
if .
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 [1].
References
[1] 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.