<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-06-24T06:28:52.517Z
2012-06-24T06:28:52.517Z
Ari
<p>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$. </p>

<p>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.</p>

<p>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?</p>

<p>(This question is inspired by <a href="https://mathoverflow.net/questions/74496/jumping-in-the-integers">this</a> recent question by Brendan McKay at Mathoverflow.)</p>

CC BY-SA 3.0
2011-09-09T03:03:06.037Z
can you add a link to the MO question ?
Suresh Venkat
CC BY-SA 3.0
2011-09-09T05:57:08.270Z
Any reason for it being a semigroup rather than a group?
Huck Bennett
CC BY-SA 3.0
2011-09-09T06:41:39.567Z
@Huck: If it is a group then Noam's construction in the link above gives such an algorithm.
Gjergji Zaimi
<cc.complexity-theory><graph-theory><ds.data-structures>
Optimal preprocessing for certain types of queries
Gjergji Zaimi
# Optimal preprocessing for certain types of queries

(Asked by: username_0 on 2011-09-09)

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](https://mathoverflow.net/questions/74496/jumping-in-the-integers) recent question by Brendan McKay at Mathoverflow.)

**Tags:** cc.complexity-theory, graph-theory, ds.data-structures

> **Comments:**
> **username_1**: can you add a link to the MO question ?  
> **username_2**: Any reason for it being a semigroup rather than a group?  
> **username_0**: @Huck: If it is a group then Noam's construction in the link above gives such an algorithm.  

---

## 1 answers

### Answer by username_3 on 2012-06-24. Score: 2

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


---

