Find interval sums with minimum number of operation

Question

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.

• greybeard: 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.

Answer 1

This problem was solved recently. The naive greedy algorithm works.

David Basin, Felix Klaedtke, Eugen Zălinescu, Greedily computing associative aggregations on sliding windows, Information Processing Letters, Volume 115, Issue 2, February 2015, Pages 186-192, ISSN 0020-0190