Wavelet tree
= Wavelet tree
A <wavelet tree> recursively partitions an alphabet and records bit sequences indicating which partition each character belongs to. A character <rank query> follows the relevant partitions while mapping the prefix length through the bit-sequence ranks. A balanced tree takes logarithmically many levels in the alphabet size.