Concepts1

Wavelet Tree

A wavelet tree is a recursive data structure built over a sequence’s alphabet that answers rank, select, and quantile (k-th smallest) queries in O(log σ) time, where σ is the number of distinct values.