Rank And Select

A bitvector with $O(1)$ rank and select: at each node, one bit per position records which half of the alphabet that symbol went to. Van Emde Boas introduced the structure in 1975 for priority queues over a bounded universe.

A bitvector with $O(1)$ rank and select: at each node, one bit per position records which half of the alphabet that symbol went to. Grossi, Gupta and Vitter introduced the structure in 2003 for compressed suffix arrays.

A Fenwick tree with $O(\log n)$ rank and select: at each node, one counter per symbol records which half of the alphabet that symbol went to. Grossi, Gupta and Vitter introduced the structure in 2003 for compressed suffix arrays.

A bitvector with $O(1)$ rank and select: at each node, one bit per position records whether that symbol is smaller than the one before it. Grossi, Gupta and Vitter introduced the structure in 2003 for compressed suffix arrays.