Operations

Bitmaps, with rank and select operations are a basic component of most compact data structures. E.g. to compactly represent the topology of a tree, a bit map is used (K2-Raster), which can be efficiently navigated by using rank operations.

Rank

Let \(B[1, n]\) be a bitmap, that is a sequence of bits from 1 to \(n\). Thus,

\[ \texttt{rank}_b(B, i) \]

returns the number of occurrences of bit \(b \in \{0, 1\}\) in \(B[1, i]\). When omitting \(b\), the \(\texttt{rank}\) operation returns the number of 1s up to a give position. That is,

\[ \texttt{rank}(B, i) \equiv \texttt{rank}_1(B, i) \]

Select

Additionally, \[ \texttt{select}_b(B, i) \] locates the position of of the $i$th occurrence of \(b\) in \(B\). These operations can be answered in constant time using just \(o(n)\) extra bits on top of \(B\).