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.