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.
