each of the small blocks it contains. The difference here is that it only needs 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 bits. A lookup table can then be used that stores the answer to every possible rank query on a bit string of length for ; this requires bits of storage space. Thus, since each of these auxiliary tables take space, this data structure supports rank queries in time and bits of space.

To answer