There is a simple representation which uses n + o(n) bits of storage space (the original bit array and an o(n) auxiliary structure) and supports rank and select in constant time. It uses an idea similar to that for range-minimum queries; there are a constant number of recursions before stopping at a subproblem of a limited size. The bit array B is partitioned into large blocks of size l = \lg^2 n bits and small blocks of size s = \lg n / 2 bits. For each large block, the rank of its first bit is stored in a separate table R_l[0 \dots n/l); each such entry takes \lg n bits for a total of (n/l) \lg n = n / \lg n bits of storage. Within a large block, another directory R_s[0 \dots l/s) stores the rank of each of the l/s = 2 \lg n small blocks it contains. The difference here is that it only needs \lg l = \lg \lg^2 n = 2 \lg \lg n bits for each entry, since only the differences from the rank of the first bit in the containing large block need to be stored. Thus, this table takes a total of (n/s) \lg l = 4 n \lg \lg n / \lg n bits. A lookup table R_p can then be used that stores the answer to every possible rank query on a bit string of length s for i \in [0, s); this requires 2^s s \lg s = O(\sqrt{n} \lg n \lg \lg n) bits of storage space. Thus, since each of these auxiliary tables take o(n) space, this data structure supports rank queries in O(1) time and n + o(n) bits of space.
