Wavelet Tree: 값 범위 이진 분할

Wavelet Tree, wavelet-tree, 웨이블릿 트리

정의

Wavelet Tree 는 시퀀스의 값 범위를 이진 분할하며 만든 트리 자료구조입니다. k-th smallest in range, rank/select, count in range 등을 O(log |Σ|) 에 답합니다.

• |Σ| = 값 범위, N = 시퀀스 길이
• 공간: O(N log |Σ|)
• 전처리: O(N log |Σ|)
• 쿼리: O(log |Σ|)

핵심 아이디어

각 레벨에서 값 범위를 반으로 나누어 왼쪽 반 (0) / 오른쪽 반 (1) 인지 비트 시퀀스를 만듭니다. 재귀적으로 각 반에 대해 반복.

input: [3 1 4 1 5 9 2 6]  (범위 [1..9])

level 0 (mid=5): [0 0 0 0 0 1 0 1]   0→[3 1 4 1 5 2], 1→[9 6]
level 1 왼쪽:    [0 0 0 0 1 0]        ... 재귀

응용

• K-th smallest in [l, r]: Persistent Segtree 대체
• Range count of values in [x, y]: O(log |Σ|)
• 문자열 접미사 배열 위 처리: LCP 등

참고

• Persistent Segtree
• Order Statistics Tree
• Suffix Array