웨이블릿 트리(구간 k번째 수) 계산기

수열의 부분구간 [l,r] 안에서 k번째로 작은 값을 빠르게 찾기 위한 것입니다. 값의 범위(0~σ−1)를 반씩 나눠 가며 각 원소가 «작은 쪽으로 갔는가»를 층마다 비트 하나로 기록해 두면, 구간 안에서 0의 개수를 세는 것(rank)만으로 다음 층에서 봐야 할 위치 구간이 정확히 정해집니다.

각 층에서 원소를 값 기준으로 나눌 때 원래 순서를 그대로 유지하기(안정 분할) 때문입니다. 그래서 구간 [l,r] 안에서 왼쪽으로 간 개수(rank)를 세면, 그 개수가 곧 다음 층 왼쪽 자식 배열에서의 새 구간 끝점이 됩니다. 순서가 흐트러지면 이 대응이 깨집니다.

루트에서 시작해 구간 [l,r]을 유지하며 내려갑니다. 이번 층에서 구간 안에 왼쪽으로 간 개수(zeros)를 세어, k가 그 이하면 답은 왼쪽 절반에 있고 새 구간은 rank 값으로 정해집니다. 아니면 k에서 zeros를 빼고 오른쪽으로 내려갑니다. 값의 범위가 층마다 반씩 줄어 log₂σ번이면 값 하나만 남는 리프에 닿습니다.

값의 범위가 매 층 절반으로 줄어들기 때문입니다. 원소 개수 n과는 무관하게, 오직 값의 종류 수 σ에만 로그로 비례해 층 수가 정해집니다. 실제 구현에서는 각 층의 비트벡터에 rank를 O(1)로 답하는 자료구조를 얹어 층당 O(1)을 만들지만, 이 계산기는 이해를 위해 단순 선형 탐색으로 rank를 계산합니다.

세그먼트 트리는 구간 합·최솟값처럼 결합법칙을 만족하는 질의에 강하고, 희소 테이블은 구간 최솟값 같은 멱등 연산의 정적 질의에 강합니다. 웨이블릿 트리는 그와 달리 «구간 안에서 몇 번째로 작은 값인가», «구간 안에 특정 값이 몇 개인가» 같은, 값의 순위와 관련된 질의에 특화되어 있습니다.

이름만 같을 뿐 전혀 다릅니다. edu/haar-wavelet은 신호를 저주파·고주파 성분으로 나누는 신호처리의 웨이블릿 변환이고, 이 도구는 정렬·순위 질의를 위한 자료구조입니다. 둘 다 "반으로 나눈다"는 아이디어를 쓰지만 목적과 수학적 배경이 다릅니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고 입력값은 이 기기에만 남습니다.