The problem with succinct data structures (and wavelet trees especially, but also rank-select dictionaries) is that while they have excellent performance characteristics when you look at them from a theoretical perspective, they tend to perform relatively poorly in practice.
This seems to be due to how much memory is accessed when checking a single bit, and the difficulty in predicting branches.
Of course it could just be that all my implementations have sucked, but even in playing around with libcds[1] didn't yield the kind of performance expected.
If anyone knows of a fast implementation of Wavelet Trees, I'd love to see it.