FIX to Rank and Select Revisited and Extended

Level: Medium

There is an error when we say that we can count the number of occurrences of a position-restricted pattern in time O(m + log log n) using O(n log^(1+e) n) bits of space. The error came from our misinterpretation of a result in computational geometry. The time is O(m + log n / log log n), and can be achieved with O(n log n) bits of space.

Fortunately this result is not very central to the paper. It is said in the Introduction and in Section 3, last lines of subsection "Larger and faster".

This issue was communicated to us by Moshe Lewenstein, Bar-Ilan University, Israel.