Find interval sums with minimum number of operation

Input:

• A list $A=a_1,\ldots,a_n$, with $\oplus$ a associative operation on $M$, and $A\subset M$.
• pairs $(s_i,t_i)$ for all $1\leq i\leq m$.

Output: The list $b_1,\ldots,b_m$, where $b_i = \bigoplus_{j=s_i}^{t_i} a_j$.

We want an efficient algorithm to compute the output, such that it uses minimum number of $\oplus$ operations.

For example, if we have $m=2$ and want to find the sum on interval $(1,n-1)$ and $(2,n)$, then the best way is to first compute $t = a_2\oplus \ldots \oplus a_{n-1}$, then compute $b_1 = a_1\oplus t$ and $b_2 = t \oplus a_n$, using $n-1$ operations.

Note it is possible that we have to use $\omega(n)$ operations, consider we have the input that contain all pairs $(i,j)$, where $1\leq i\leq j\leq n$. This would require at least ${n \choose 2}$ operations, because there could be ${n \choose 2}$ different values.

Assume all elements in $M$ take $O(1)$ space. We also want to use as little additional memory as possible.

• Seems easier to me if there was $⊕^{-1}$. A no-brainer requiring $O(n)$ space would be to combine $2^n$ values (0 < n < $ld |M|$), which wouldn't do half bad to support independent queries. For the set problem (all pairs known from the outset), it looks clumsy and weak. Commented Mar 14, 2015 at 8:18