Wavelet Trees Meet Suffix Trees

Maxim Babenko, Paweł Gawrychowski, Tomasz Kociumaka +1

We present an improved wavelet tree construction algorithm and discuss its applications to a number of rank/select problems for integer keys and strings. Given a string of length n…