I'm going to give a lecture on Alon and Schieber's Tech Report on computing semigroup products (Optimal Preprocessing for Answering On-Line Product Queries). Basically, given a list of elements $a_1,\ldots,a_n$ and a bound $k$, they show how to preprocess the elements so that later it is possible to efficiently compute the product of any arbitrary sublist $a_i\cdot\ldots\cdot a_j$ by performing only $k$ products.
To motivate this algorithm I am looking for examples of semigroups where: 1. It is plausible that one would have a list of elements and want to compute products of sublists. 2. The semigroup is not a group (since the problem is trivial for groups). 3. The space complexity of the product does not overwhelm the time complexity of computing it directly (e.g., in string concatenation, just copying the result to the output takes the same time as computing it even with no preprocessing).
So far I only have $\min$ and $\max$ and matrix multiplication as examples. I'm looking for something more "sexy", preferably related to Computer Science (perhaps something to do with graphs or trees). Also, for $\min$ and $\max$ there is a better algorithm, so I can't really use them to motivate this algorithm.