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?


closed as too broad by user6973, Mohammad Al-Turkistany, Kaveh, D.W., Sasho Nikolov Jan 4 '17 at 10:33

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ binary search ​ ​ $\endgroup$ – user6973 Jan 3 '17 at 0:47
  • 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

Not the answer you're looking for? Browse other questions tagged or ask your own question.