  We examine the amount of preprocessing needed for answering certain on-line
queries as fast as possible. We start with the following basic problem. Suppose
we are given a semigroup $(S,\circ )$. Let $s_1 ,\ldots, s_n$ be elements of
$S$. We want to answer on-line queries of the form, ``What is the product $s_i
\circ s_{i+1} \circ \cdots \circ s_{j-1} \circ s_j$?'' for any given $1\le i\le
j\le n$. We show that a preprocessing of $\Theta(n \lambda (k,n))$ time and
space is both necessary and sufficient to answer each such query in at most $k$
steps, for any fixed $k$. The function $\lambda (k,\cdot)$ is the inverse of a
certain function at the $\lfloor {k/2}\rfloor$-th level of the primitive
recursive hierarchy. In case linear preprocessing is desired, we show that one
can answer each such query in $O( \alpha (n))$ steps and that this is best
possible. The function $\alpha (n)$ is the inverse Ackermann function.
  We also consider the following extended problem. Let $T$ be a tree with an
element of $S$ associated with each of its vertices. We want to answer on-line
queries of the form, ``What is the product of the elements associated with the
vertices along the path from $u$ to $v$?'' for any pair of vertices $u$ and $v$
in $T$. We derive results that are similar to the above, for the preprocessing
needed for answering such queries.
  All our sequential preprocessing algorithms can be parallelized efficiently
to give optimal parallel algorithms which run in $O(\log n)$ time on a CREW
PRAM. These parallel algorithms are optimal in both running time and total
number of operations.
  Our algorithms, especially for the semigroup of the real numbers with the
minimum or maximum operations, have various applications in certain graph
algorithms, in the utilization of communication networks and in Database
retrieval.
