5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – greybeard Mar 14 '15 at 8:18
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.