This paper presents efficient preprocessing algorithms for answering product queries on linear and tree structures. For linear product queries, given a semigroup (S, ∘) and a sequence of elements s₁, ..., sₙ, the goal is to answer queries of the form "What is the product s_i ∘ s_{i+1} ∘ ... ∘ s_j?" for any 1 ≤ i ≤ j ≤ n. The preprocessing time and space required to answer each query in at most k steps is Θ(nλ(k, n)), where λ(k, ·) is the inverse of a certain function at the ⌊k/2⌋-th level of the primitive recursive hierarchy. For linear preprocessing, each query can be answered in O(α(n)) steps, where α(n) is the inverse Ackermann function, and this is optimal. For tree product queries, given a tree T with elements of S associated with its vertices, the goal is to answer queries of the form "What is the product of the elements along the path from u to v?" for any pair of vertices u and v in T. The preprocessing time and space required to answer each query in at most 2k steps is also Θ(nλ(k, n)). For linear preprocessing, each query can be answered in O(α(n)) steps, which is optimal. The algorithms are efficient and can be parallelized to run in O(log n) time on a CREW PRAM. They are optimal in both running time and total number of operations. The algorithms have applications in graph algorithms, communication networks, and database retrieval. The paper also discusses open problems, including dynamic updates to the input data.This paper presents efficient preprocessing algorithms for answering product queries on linear and tree structures. For linear product queries, given a semigroup (S, ∘) and a sequence of elements s₁, ..., sₙ, the goal is to answer queries of the form "What is the product s_i ∘ s_{i+1} ∘ ... ∘ s_j?" for any 1 ≤ i ≤ j ≤ n. The preprocessing time and space required to answer each query in at most k steps is Θ(nλ(k, n)), where λ(k, ·) is the inverse of a certain function at the ⌊k/2⌋-th level of the primitive recursive hierarchy. For linear preprocessing, each query can be answered in O(α(n)) steps, where α(n) is the inverse Ackermann function, and this is optimal. For tree product queries, given a tree T with elements of S associated with its vertices, the goal is to answer queries of the form "What is the product of the elements along the path from u to v?" for any pair of vertices u and v in T. The preprocessing time and space required to answer each query in at most 2k steps is also Θ(nλ(k, n)). For linear preprocessing, each query can be answered in O(α(n)) steps, which is optimal. The algorithms are efficient and can be parallelized to run in O(log n) time on a CREW PRAM. They are optimal in both running time and total number of operations. The algorithms have applications in graph algorithms, communication networks, and database retrieval. The paper also discusses open problems, including dynamic updates to the input data.