Minimum number of operations to execute an associative operations on overlapping sets

Question

Let V be an array of elements belonging to a domain D (e.g. integer numbers)

V = {v1, v2, ..., vN}

Let f(x,y) be a binary operator z=f(x,y) defined in [DxD]->D.

f is associative and commutative.

f does not support inverse on its full domain, i.e. if the result z and one of the arguments x or y is known, it is not always possible to obtain the other argument.

Given an ordered pair of indices (i,j), the operator g(i,j) is defined as the reduction of the sub array {vi, ..., vj} obtained with operator f.

For example, if f is the multiplication operator, i.e. f(x,y)=x*y, then

g(2,5) = v2 * v3 * v4 * v5

I need to compute the functional g on a large set of pairs (i,j), which involve overlapping elements of the vector V.

I would like to take advantage of the associativity of operator f to perform this computation with the minimum possible number of applications of the operator f, because f is computationally very expensive.

For example, sticking to the example above, where f is integer multiplication, given an array V with 5 entries and the pairs of indices (1,3), (2,4), (2,5), (1,4), I can compute all pairs with 6 multiplicatons:

V={1, 2, 0, 3, 5}

1. V12 = V1 * V2
2. V13 = V12 * V3   // pair (1,3)
3. V14 = V13 * V4   // pair (1,3)
4. V23 = V2 * V3
5. V24 = V23 * V4   // pair (2,4)
6. V25 = V24 * V5   // pair (2,5)

Can anybody suggest an algorithm to derive the optimal computation graph, as I did manually above? I know the solution to the problem is not unique. Any minimal solution would do. Even a heuristic pseudo-optimal solution would do.

Answer 1

This problem is sometimes called the range semigroup query problem or the partial sums problem and there are some amazingly fast solutions to it. These slides derive a solution that does nα(n) preprocessing applications of f and supports queries making α(n) calls to f, where α is the inverse Ackermann function. There's also a paper detailing an even faster approach. Hopefully these can get you started in the right direction!