Wavelet tree 是一種資料結構，它將字串逐漸分割直到字串只由一種字元組成為止。並且可以用來解決超過兩個字元的 rank 跟 select 問題。

建立 tree 的範例

一個由數字  ∈ Σ = [0:9], ∥Σ∥ = σ 組成的字串（或是序列） S ：

S = (4,5,6,7,2,0,6,1,6,9,9,0,8,3,1)

1. 先找到 S 中不重複字元（[0:9]）的中位數 p（5），然後將所有小於 p 的字元用 0 表示， 其他的則用 1 表示，得到二元序列（binary sequence）B：

   B = (0,1,1,1,0,0,1,0,1,1,1,0,1,0,1)

2. 接著將用 0 表示的字元收集成一個序列，作為一個子樹的根（root）；用 1 表示的字元收集成一個序列，作為另一個子樹的根。

   $$ S_0 = (4, 2, 0, 1, 0, 3, 1) \\ S_1 = (5, 6, 7, 6, 6, 9, 9, 8) $$

3. 再來重複 1. 直到 S 中只有一種字元為止。

最後的樹如下：

注意在實際情形下，每個節點都不需要紀錄它的 S，只需要紀錄 B 就夠了。

應用

假設

• 以下兩種 query 必須用到對二元序列的 rank 與 select 都能在 O(1) 完成的假設（可以利用 Four Russians 的方法解決）。
• 所有序列的編號（index）都從 1 開始計算。

O(logσ) rank

rank(a,i)：在 S[1:i] 中，字元 a 出現的次數。

1. 從根開始
2. 找到 a 在這個節點代表的bit b。
3. 對 B 更新 i = rank(b,i)。
4. 走標記為 b 的連結到下一層的節點。
5. 重複2. 3. 4. 直到走到葉子（leaf）。
6. 回傳這時的 i。

例如計算 rank(6,9)（在 S[1:9] 中，字元 6 出現的次數）時，走過的節點與 i 的變化會是這樣：

O(logσ) select

select(a,j)：在 S 中，第 j 個 a 出現的位置。

1. 從都是 a 的葉子開始，如果 j 大於 B 的長度，回傳 0。
2. 經由標記為 b 的連結往上走到上層的節點。
3. 對 B 更新 j = select(b,j)。
4. 重複2. 3. 直到到達樹的根。
5. 回傳這時的 j。

例如計算 select(6,2)（在 S 中，第 2 個 6 出現的位置）時，走過的節點與 j 的變化如下：

以上兩種 query 由於都只經過 O(h) = O(logσ) 個節點，所以時間複雜度為 O(logσ)。

參考資料

1. Gonzalo Navarro - Wavelet Trees for All
2. Wikipedia - Wavelet Tree
3. Alex Bowe - Wavelet Trees – an Introduction