Optimal preprocessing for certain types of queries

Question

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.)

Answer 1

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.