The Art Gallery Guardian

Finger tree allowing apply functions to each element


Let (M,+)(M,+) be a monoid. We are interested in maintaining a sequence a=a1,,anMa = a_1,\ldots,a_n\in 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=f1,,fnMMf = f_1,\ldots,f_n\in M\to M.

The functions satisfies the following property.

f1(x1)++fn(xn)=f1(y1)++fn(yn)f_1(x_1)+\ldots+f_n(x_n) = f_1(y_1)+\ldots+f_n(y_n) if i=1nxi=i=1nyi\sum_{i=1}^n x_i = \sum_{i=1}^n y_i.

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

  • evaluate(X): It returns f1(x1)++fn(xn)f_1(x_1) + \ldots +f_n(x_n) for any sequence x1,,xnx_1,\ldots,x_n such that i=1nxi=X\sum_{i=1}^n x_i = X.
  • split(j): returns a representation for f1,,fjf_1,\ldots,f_j and fj+1,,fnf_{j+1},\ldots,f_n.

We are interested in implementing FunctionUpdate(a,f), the output would be a representation of the sequence f1(a1),,fn(an)f_1(a_1),\ldots,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 a1,,ana_1,\ldots,a_n, such that we can do the operation inc(i,j)inc(i,j), which increment all numbers from iith to jjth index by 11. That is, the new sequence is a1,,ai1,ai+1,,aj+1,aj+1,,ana_1,\ldots,a_{i-1},a_i+1,\ldots,a_j+1,a_{j+1},\ldots,a_n. Also, it has a function value(i)value(i) which returns aia_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

[1] H. Booth, R. Tarjan, Finding the minimum-cost maximum flow in a series-parallel network, Journal of Algorithms. 15 (1993) 416–446 10.1006/jagm.1993.1048.

Posted by Chao Xu on 2019-03-10.
Tags: data structure, lazy propagation.