The Wavelet Tree is a succinct data structure to store strings in compressed space. It generalizes the rank query and select query operations defined on bitvectors to arbitrary alphabets. - View it on GitHub