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.
New to topics? Read the docs here!