# Finger tree allowing apply functions to each element

Let $(M,+)$ be a monoid. We are interested in maintaining a sequence $a=a_{1},…,a_{n}∈M$ under all updates currently supported by finger tree. However, we are also interested in adding another update, which we call the function update.

Let $f=f_{1},…,f_{n}∈M→M$.

The functions satisfies the following property.

$f_{1}(x_{1})+…+f_{n}(x_{n})=f_{1}(y_{1})+…+f_{n}(y_{n})$ if $∑_{i=1}x_{i}=∑_{i=1}y_{i}$.

The sequence $f$ is given implicitly, where it has two methods:

`evaluate(X)`

: It returns $f_{1}(x_{1})+…+f_{n}(x_{n})$ for any sequence $x_{1},…,x_{n}$ such that $∑_{i=1}x_{i}=X$.`split(j)`

: returns a representation for $f_{1},…,f_{j}$ and $f_{j+1},…,f_{n}$.

We are interested in implementing `FunctionUpdate(a,f)`

,
the output would be a representation of the sequence $f_{1}(a_{1}),…,f_{n}(a_{n})$.

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 $a_{1},…,a_{n}$, such that we can do the operation $inc(i,j)$, which increment all numbers from $i$th to $j$th index by $1$. That is, the new sequence is $a_{1},…,a_{i−1},a_{i}+1,…,a_{j}+1,a_{j+1},…,a_{n}$. Also, it has a function $value(i)$ which returns $a_{i}$. 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

**Finding the minimum-cost maximum flow in a series-parallel network**, Journal of Algorithms. 15 (1993) 416–446 10.1006/jagm.1993.1048.