<ul>
<li>As Ricky Demer said in his comment, many search problems can be sped up with sorting or building some other index structure</li>
<li>Lowest common ancestor queries can be answered in constant time with linear preprocessing.</li>
<li>Lots of text problems can be sped up with some preprocessing, e.g. building a suffix array</li>
</ul>

CC BY-SA 3.0
2017-01-03T09:10:08.063Z
2017-01-03T09:10:08.063Z
adrianN
<p>In celebrated paper <em>Clustered integer 3SUM via additive combinatorics</em> 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.</p>

<p>What other examples of such algorithms in preprocessed universe do you know?</p>

<ds.algorithms><ds.data-structures><online-algorithms><fine-grained>
Algorithms in preprocessed universe
ivmihajlin
# Algorithms in preprocessed universe

(Asked by: username_0 on 2017-01-02)

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?

**Tags:** ds.algorithms, ds.data-structures, online-algorithms, fine-grained

---

## 1 answers

### Answer by username_1 on 2017-01-03. Score: 2

* 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


---

