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?

Improve this question
$\endgroup$
1
  • 4
    $\begingroup$ binary search ​ ​ $\endgroup$
    – user6973
    Commented Jan 3, 2017 at 0:47

1 Answer 1

Reset to default
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
Improve this answer
$\endgroup$

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