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.
Articles by others on the same topic
There are currently no matching articles.