4
$\begingroup$

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?

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

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