개요Wavelet Tree는 **문자열이나 시퀀스에서 순위(rank), 선택(select), 구간 빈도(range frequency)**와 같은 질의를 빠르게 처리할 수 있도록 설계된 이진 트리 기반의 압축 인덱스 자료구조입니다. 본래 압축 텍스트 인덱싱을 위해 개발되었으나, 현재는 생물정보학, 정보 검색, 문자열 알고리즘 등 다양한 분야에서 활용되고 있습니다.1. 개념 및 정의Wavelet Tree는 입력 시퀀스를 여러 레벨의 이진 트리로 분해하고, 각 노드에 비트 벡터를 저장하여 특정 질의를 O(log σ) 시간에 처리할 수 있도록 구성됩니다.입력: 길이 n의 시퀀스 S over alphabet Σ트리 구조: 알파벳 구간을 기준으로 분할된 이진 트리노드 데이터: 현재 구간 내 요소의 분할 여부를 나타..