Algorithms in preprocessed universe In celebrated paper Clustered integer 3SUM via additive combinatorics by TM Chan and M Lewenstein one of the provided algorithms is the one for preprocessed universe.   They were able to provide an algorithm with running time $O(n^{13/7})$ for solving 3-Sum on the subset of the universe of size $n$, assuming some preprocessing was allowed.

What other examples of such algorithms in preprocessed universe do you know?
As Ricky Demer said in his comment, many search problems can be sped up with sorting or building some other index structure
Lowest common ancestor queries can be answered in constant time with linear preprocessing.
Lots of text problems can be sped up with some preprocessing, e.g. building a suffix array