There is a string T of length n on alphabet A={1,2,…,σ}.
From T, we create σ bit-vectors Bc for c∈A so that Bc[i] = 1 if and only if T[i] = c.
How to prove that using these bit-vectors and auxiliary data structures, rank and select on T are done in constant time?
We knew use Wavelet Tree can do rank and select in O(lgσ)time, but how to it in constant time?
New contributor
user24728078 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.