Sequence representations supporting the queries access, select, and rank are at
the core of many data structures. There is a considerable gap between the
various upper bounds and the few lower bounds known for such representations,
and how they relate to the space used. In this article, we prove a strong lower
bound for rank, which holds for rather permissive assumptions on the space
used, and give matching upper bounds that require only a compressed
representation of the sequence. Within this compressed space, the operations
access and select can be solved in constant or almost-constant time, which is
optimal for large alphabets. Our new upper bounds dominate all of the previous
work in the time/space map.