Optimal preprocessing for certain types of queries 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.)
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&lt;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.