Wavelet Tree

Recursively split the alphabet — one bitvector per level — and answer access / rank / quantile in O(log σ)

Query: O(log σ)
Build: O(n log σ)
Space: n·log₂σ bits
σ (alphabet): 16
levels: 4

Sequence & Build

Queries

Slow Fast
bit 0 (lower half → left) bit 1 (upper half → right) in current range node on query path answer

Wavelet Tree — alphabet split per level

Step Info

Press Build, then run a query and watch it descend.

Big-O

OperationTimeNote
buildO(n log σ)one pass per level
access(i)O(log σ)read one bit per level
rank_c(i)O(log σ)follow bits of c
quantile(l,r,k)O(log σ)carry range, compare k
rangeCountO(log σ)countLess descent
spacen·⌈log₂σ⌉ bitssuccinct (+o())

Operation Log