# Algorithms in preprocessed universe [closed]

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?

• binary search ​ ​ – user6973 Jan 3 '17 at 0:47

## 1 Answer

• 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