The paper examines the amount of preprocessing required to answer certain online queries as efficiently as possible. Specifically, it focuses on two types of queries: linear product queries and tree product queries. For linear product queries, the goal is to answer queries of the form "What is the product \( s_i \circ s_{i+1} \circ \cdots \circ s_j \)" for given elements \( s_1, \ldots, s_n \) in a semigroup \( (S, \circ) \). For tree product queries, the goal is to answer queries of the form "What is the product of the elements associated with the vertices along the path from vertex \( u \) to vertex \( v \)" in an unrooted tree \( T \). The authors present efficient preprocessing algorithms for both types of queries. For linear product queries, they show that a preprocessing of \( \Theta(n \lambda(k, n)) \) time and space is both necessary and sufficient to answer each query in at most \( k \) steps, where \( \lambda(k, \cdot) \) is the inverse of a certain function at the \( \lfloor k/2 \rfloor \)-th level of the primitive recursive hierarchy. They also provide a linear preprocessing algorithm that enables answering each query in \( \mathcal{O}(\alpha(n)) \) steps, where \( \alpha(n) \) is the inverse Ackermann function. For tree product queries, they show that a preprocessing of \( \mathcal{O}(n \lambda(k, n)) \) time and space is sufficient to answer each query in at most \( 2k \) steps. The paper also discusses the parallelization of these sequential preprocessing algorithms, demonstrating that they can be efficiently parallelized to run in \( \mathcal{O}(\log n) \) time on a CREW PRAM. These parallel algorithms are optimal in both running time and total number of operations. The authors establish a trade-off between the preprocessing time and the query answering time, showing that for linear product queries, answering each query in at most two steps requires \( \Theta(n \log n) \) preprocessing time, while allowing four computation steps per query reduces the preprocessing time to \( \mathcal{O}(n \log^4 n) \). Similarly, for tree product queries, answering each query in at most two steps requires \( \Omega(n \lambda(2k, n)) \) preprocessing time, while allowing four computation steps per query reduces the preprocessing time to \( \mathcal{O}(\alpha(n)) \). The paper concludes with a discussion of potential applications of these algorithms in graph algorithms, communication networks, and database retrieval, and outlines open problems related to dynamic operations and further applications.The paper examines the amount of preprocessing required to answer certain online queries as efficiently as possible. Specifically, it focuses on two types of queries: linear product queries and tree product queries. For linear product queries, the goal is to answer queries of the form "What is the product \( s_i \circ s_{i+1} \circ \cdots \circ s_j \)" for given elements \( s_1, \ldots, s_n \) in a semigroup \( (S, \circ) \). For tree product queries, the goal is to answer queries of the form "What is the product of the elements associated with the vertices along the path from vertex \( u \) to vertex \( v \)" in an unrooted tree \( T \). The authors present efficient preprocessing algorithms for both types of queries. For linear product queries, they show that a preprocessing of \( \Theta(n \lambda(k, n)) \) time and space is both necessary and sufficient to answer each query in at most \( k \) steps, where \( \lambda(k, \cdot) \) is the inverse of a certain function at the \( \lfloor k/2 \rfloor \)-th level of the primitive recursive hierarchy. They also provide a linear preprocessing algorithm that enables answering each query in \( \mathcal{O}(\alpha(n)) \) steps, where \( \alpha(n) \) is the inverse Ackermann function. For tree product queries, they show that a preprocessing of \( \mathcal{O}(n \lambda(k, n)) \) time and space is sufficient to answer each query in at most \( 2k \) steps. The paper also discusses the parallelization of these sequential preprocessing algorithms, demonstrating that they can be efficiently parallelized to run in \( \mathcal{O}(\log n) \) time on a CREW PRAM. These parallel algorithms are optimal in both running time and total number of operations. The authors establish a trade-off between the preprocessing time and the query answering time, showing that for linear product queries, answering each query in at most two steps requires \( \Theta(n \log n) \) preprocessing time, while allowing four computation steps per query reduces the preprocessing time to \( \mathcal{O}(n \log^4 n) \). Similarly, for tree product queries, answering each query in at most two steps requires \( \Omega(n \lambda(2k, n)) \) preprocessing time, while allowing four computation steps per query reduces the preprocessing time to \( \mathcal{O}(\alpha(n)) \). The paper concludes with a discussion of potential applications of these algorithms in graph algorithms, communication networks, and database retrieval, and outlines open problems related to dynamic operations and further applications.