11
$\begingroup$

Suppose we have a semigroup $(S,\circ)$ with elements $S=\lbrace s_1,s_2,\dots,s_n\rbrace$. Our goal is to compute products $s_i\circ s_{i+1}\circ \cdots\circ s_j$.

In their paper "Optimal Preprocessing for answering on-line product queries" Alon and Schieber prove that we can answer each such query in at most $O(\alpha(n))$ steps (where $\alpha$ is the inverse Ackermann function) by using only linear amount of preprocessing.

If it is desired that each query $s_i\circ s_{i+1}\circ \cdots\circ s_j$ can be answered in $O(\log(j-i))$ steps, can one still do this with only linear preprocessing?

(This question is inspired by this recent question by Brendan McKay at Mathoverflow.)

$\endgroup$
  • 1
    $\begingroup$ can you add a link to the MO question ? $\endgroup$ – Suresh Venkat Sep 9 '11 at 3:03
  • 1
    $\begingroup$ Any reason for it being a semigroup rather than a group? $\endgroup$ – Huck Bennett Sep 9 '11 at 5:57
  • 1
    $\begingroup$ @Huck: If it is a group then Noam's construction in the link above gives such an algorithm. $\endgroup$ – Gjergji Zaimi Sep 9 '11 at 6:41
2
$\begingroup$

Construct an ordered balanced binary tree with $s_1,\dots,s_n$ in the leaves (in order). In each internal node $v$ store the product of the leaves of the subtree rooted at $v$. This preprocessing obviously runs in O$(n)$ time and space.

Now, to compute a product $s_i\circ\ldots\circ s_j$ (where $i<j$) walk the tree up from $i$ to the least common ancestor (LCA) of $i$ and $j$. Collect the products stored in each right child hanging off the path, excluding the right child of the LCA. In other words, as you go up from $u$ to its parent $v$, if $u$ is a left child of $v$, then pick up the product stored in $v$'s right child. Similarly, walk up from $j$ to the LCA and collect the products stored in left children hanging off that path. Multiply all these products, along with $s_i$ and $s_j$ in order.

$\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.