Algorithms in preprocessed universe
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