인터벌 트리를 위한 펜윅 레이아웃

인터벌 트리를 위한 펜윅 레이아웃

2025년 9월 10일

펜윅 트리(Fenwick tree)와 인터벌 트리(interval tree)는 컴퓨터 과학에서 잘 알려진 자료구조입니다. 특히 인터벌 트리는 생물정보학과 계산기하에서 흔히 쓰이며, 펜윅 트리는 통계 집계에 유용합니다.

이 글은 두 자료구조를 결합해 최악의 경우 더 빠른 인터벌 트리 구현을 얻는 방법을 설명합니다. 이런 분야들의 특수한 요구 사항에는 크게 맞지 않을 수 있지만, 그래도 범용으로 잘 통하는 구현이며, 깔끔하고 짧아서 공유하고 싶었습니다.

TL;DR 주제에 익숙하다면: 인터벌 트리의 노드를 고유한 중심값으로 인덱싱하고, 트리 위에서 펜윅 트리처럼 빠르게 이동할 수 있습니다. 예시 구현은 GitHub에 있습니다.

이하에서는 이 아이디어를 자세히 풀이합니다. 기본적인 자료구조·알고리즘(DsA)에 익숙하다고 가정하지만, 위 자료구조들을 꼭 알고 있을 필요는 없습니다.

인터벌 트리

인터벌 트리는 구간을 저장하는 자료구조입니다(이 글에서는 반열린 구간 [a;b), 0≤a<b≤M 을 사용). 질의 “주어진 점 x를 포함하는 구간은 무엇인가?”를 효율적으로 처리합니다. 인터벌 트리는 𝒪(n log n) 시간에 구축할 수 있고, 𝒪(log min(n,M) + ans) 시간에 질의에 응답하며, 𝒪(n) 공간을 사용합니다.

인터벌 트리는 이진 트리를 바탕으로 합니다. 루트 노드는 전체 범위 [0;M) 를 담당하며, 중앙점 m(정확한 중간일 필요는 없음)에서 둘로 나눠 [0;m) 과 [m;M) 두 자식으로 분할하고, 이를 재귀적으로 반복합니다. 각 노드는 구간들의 리스트를 저장합니다. 초기화 시 각 구간은 중심 m이 [a;b) 안에 들어가는 “가장 높은” 노드에 배치됩니다. 노드는 필요할 때만 생성하며, 비어 있는 서브트리는 생략합니다.

이것은 상향식이 아닌 상향식?이 아니라 탑다운으로 쉽게 구현됩니다. 적절한 노드를 반복적으로 찾아 내려가며, b≤m 이면 왼쪽 자식으로, a>m 이면 오른쪽 자식으로, 그 외(즉 a≤m<b)이면 현재 노드에 구간을 추가합니다.

모든 구간은 자신이 속한 노드의 범위 안에 있으므로, 점 x 를 포함하는 모든 구간은 x 를 덮는 𝒪(log n) 개의 노드 중 하나에 반드시 존재합니다. 이 노드들은 반복적으로 찾아낼 수 있습니다. 그런데 이게 무슨 도움이 되느냐고요? 원점으로 돌아간 것 같지 않나요?

그렇지 않습니다. 각 노드의 구간들은 중심 m을 포함하므로 a≤m<b 가 성립합니다. 예를 들어 x<m 이라면 x<b 가 자동으로 참이므로 a≤x 만 검사하면 됩니다. 비슷하게 x>m 이라면 x<b 만 검사하면 되고, x=m 이라면 모든 구간이 일치합니다. 하나의 조건으로만 거르는 것은 두 조건보다 훨씬 쉽습니다. 리스트를 두 개 두면 되기 때문이죠: 하나는 a 기준 오름차순, 다른 하나는 b 기준 오름차순.

우리는 일치하는 구간을 모두 출력해야 하므로 이 리스트들에 이진 탐색을 돌릴 필요가 없습니다. 리스트를 선형으로 순회하면서 처음 불일치가 나오면 멈추고, 그 전까지의 구간을 탐욕적으로 모두 내보내면 됩니다.

인터벌 트리는 여러 변형이 있습니다. 예컨대 질의 구간과 교차하는 모든 구간 찾기, 더 높은 차원의 공간 지원, 정렬된 배열 대신 이진 트리를 써서 구간의 동적 삽입/삭제를 지원하는 것 등이 있습니다.

앞서 언급한 전통적인 적용 분야 말고, 다소 엉뚱한 용례도 덧붙이고 싶습니다.

첫 번째는 제가 예전에 쓴 글입니다. 인터벌 트리를 보조 자료구조로 써서, CFG 없이 제어 흐름을 디컴파일하는데 최악 시간 복잡도를 아(부분)제곱보다 낮게 유지합니다.

두 번째는 파티 트릭입니다. 정점 집합 V={0,1,…,n−1}, 간선 집합 E 인 그래프가 있는데, 간선이 한 정점에서 한 정점으로 가는 게 아니라 정점 구간 [a;b) 에서 단일 정점 v 로 간다고 합시다. DFS 를 이 그래프에서 수행할 때, 시간 복잡도를 제곱으로 만들지 않으려면 간선을 인터벌 트리에 저장하세요. 그리고 정점 u 의 이웃을 찾을 때, u 를 포함하는 구간에 대응하는 v 들을 조회합니다. 그런 다음 해당 구간들을 인터벌 트리에서 제거하세요. 그러면 ∑ans = 𝒪(E) 가 되고, 전체 시간 복잡도는 𝒪(V log V + E) 가 됩니다. 제거를 위해 복잡한 구현이 필요하지도 않습니다. 방출한 인덱스의 접두/접미 부분을 그냥 버리면 됩니다.

이론적으로는 균형 이진 트리라면 무엇이든 인터벌 트리의 바탕이 될 수 있습니다. 하지만 현실 구현에서는 상수항, 캐시 친화성, 공간 사용량, 분기 예측 등도 고려해야 합니다. 보통은 균형 트리가 단순할수록 성능이 좋습니다. AVL 은 단순하지 않기 때문에, 저는 다른 길을 찾았습니다.

세그먼트 트리

세그먼트 트리. 이름은 “인터벌 트리”와 비슷하지만, 속지 마세요. 세그먼트 트리는 별개의 고전 자료구조이며, 경쟁 프로그래밍 밖에서는 잘 알려져 있지 않습니다. 세그먼트 트리는 배열에 대한 구간 질의(예: 구간 합, 구간 최소 질의)를 최적화하는 데 쓰이며, 누적 히스토그램, 다양한 트리 알고리즘, 여러 즉석 문제들에 유용합니다.

핵심 아이디어는 데이터가 조밀할 때는 자가 균형 트리보다 정적 균형 트리 레이아웃이 더 빠르다는 점입니다. 정적 트리는 상황에 적응하는 능력이 떨어지지만, 상황이 미리 정해져 있다면 균형 메커니즘은 점근적으로 사소하더라도 쓸데없는 짐일 뿐입니다.

이 자료구조는 완전 이진 트리입니다(배열 크기를 사실상 2의 거듭제곱으로 올림). 각 노드는 정확히 중앙 m = (l + r) / 2 에서 분할됩니다. 노드는 추가/삭제하지 않고, 순회만 합니다. 각 리프 노드는 배열의 한 원소를 저장하며, 인덱스를 명시적으로 저장하지 않습니다. 질의는 일반적인 자가 균형 트리와 같은 방식으로 처리합니다.

이때 완전 이진 트리의 노드들을 Eytzinger 레이아웃으로 저장할 수 있습니다. 이는 자식 포인터를 저장하지 않고도 부모 인덱스로부터 자식 인덱스를 “계산”할 수 있게 해줍니다. 노드 v 의 두 자식은 2v 와 2v+1 로 정의되며, v=1 이 루트입니다. 이렇게 하면 공간도 절약되고, 접근 성능과 캐시 친화성도 좋아집니다. 자식 인덱스를 얻기 위해 메모리를 읽지 않아도 되고, 트리의 상위 레벨 노드들이 배열의 앞부분에 밀집해 있기 때문입니다.

이 혜택을 합치면, 조밀하지 않은 데이터에 대해서도 어떤 자가 균형 트리보다 더 잘 동작하는 경우가 많습니다. (또한 자식 수를 2보다 크게 확장해 SIMD 이점을 살릴 수 있습니다. 넓은 세그먼트 트리는 세그먼트 트리에 대한 B-트리의 관계와 비슷합니다.)

다음으로 강조하고 싶은 세그먼트 트리의 특징이 하나 더 있습니다. 레이아웃이 고정되어 있으므로, 노드 [x;x+1) 의 인덱스를 즉시 v=n+x 로 계산할 수 있습니다(여기서 n 은 배열의 크기). 주어진 노드의 부모는 ⌊v/2⌋ 로 계산할 수 있습니다. 이 덕분에 x 를 포함하는 노드들을 전형적인 탑다운이 아니라 보텀업 순서로 순회할 수 있어, 어느 자식으로 재귀할지 결정하는 비교/분기를 절약합니다.

그런데, 우리는 세그먼트 트리가 아니라 펜윅 트리를 쓰려는 게 아니었나요?

펜윅 트리

이렇게 정의되는 경우는 드물지만, 펜윅 트리는 사실 세그먼트 트리의 최적화 변종입니다. (이 사실을 강조하는 자료로 제가 아는 것은 Brent Yorgey의 글뿐입니다. 감사!)

펜윅 트리의 아이디어는, 질의가 접두사에 대해서만 수행되는 한, 부모의 “오른쪽 자식”인 노드들은 결코 접근되지 않는다는 점(단, 순회 경로상 지나갈 수는 있음)입니다. 이는 두 가지를 의미합니다. a) 노드의 절반을 제거해 공간을 절약할 수 있다. b) 각 노드는 서로 다른 “오른쪽 좌표”를 갖는다. 즉, 노드의 끝점(우측 경계)을 노드의 인덱스로 쓸 수 있습니다.

보통 세그먼트 트리를 구현할 때는 현재 노드 인덱스와 그 범위를 함께 저장해야 하지만, 둘이 동일하다면 수식을 크게 단순화할 수 있습니다. 노드 인덱스의 비트 표현이 많은 정보를 담고 있다는 점이 드러납니다. 존재하는 리프의 끝 좌표는 항상 …1 로 끝나고, 그 부모는 …10, 그 위 부모는 …100, 이런 식입니다. 이로써 인덱스만으로 노드의 깊이를 쉽게 계산할 수 있습니다.

비슷하게, 단순한 비트 트릭으로 몇 비트를 지우거나 더해 주기만 하면, 존재하는 가장 가까운 조상이나 왼쪽 자식의 인덱스도 계산할 수 있어, 세그먼트 트리를 매우 빠르게 구현할 수 있습니다. 세부 사항은 이 글의 주제가 아니므로 생략하지만, 관심 있다면 “Fenwick tree”를 찾아보세요.

중요한 점은, 펜윅 트리는 세그먼트 트리와 비교해 치명적인 결점이 하나 있다는 것입니다. 최상위 노드들이 서로 멀리 떨어진 메모리 위치에 저장되므로, 중간 크기에서는 캐시 친화성이 떨어집니다. 그래도 결국엔 저장해야 할 데이터가 절반이고 알고리즘이 단순해서 이득이지만, 언급해 둘 가치가 있습니다. 또한 SIMD 로 최적화한 넓은 세그먼트 트리보다는 느립니다. 이것은 자명하겠죠.

더 나은 인터벌 트리

우리가 펜윅 트리에서 차용할 구체적 아이디어는, 불필요한 노드를 버리면서 보조 인덱스를 그 노드의 고유 성질로 대체한다는 것입니다. 인터벌 트리에서 그 “고유 성질”은 노드의 중심 m 입니다. 두 노드가 같은 중심을 공유한다면 가장 위의 노드만 남기면 됩니다.

잠시 M 이 2의 거듭제곱으로 반올림되어 있다고 가정합시다. 루트 노드의 인덱스는 M/2, 즉 100…00(이진)입니다. 그 자식들은 010…00 과 110…00 이고, 계속 이렇습니다. 끝자리의 0 개수(후행 0의 개수)가 노드의 높이에 대응합니다.

문제를 둘로 나눠 생각해 봅시다. 점 x 에 대한 질의는 x 를 포함하는 모든 노드를 루트부터 시작해 m=x 인 노드에 도달할 때까지 순회합니다. 우리는 반대로 할 수 있습니다. 노드 x 에서 시작해 위로 올라가는 것이죠.

비트 패턴 a b c d 100…0 인 노드는 그 끝 0 의 개수만큼의 높이를 가지므로, 그 범위는 [a b c d 000…0; a b c d 111…1] 입니다. 이 노드의 부모는 [a b c 0000…0; a b c 1111…1] 범위를 갖고, 중심은 a b c 1000…0 입니다. 따라서 노드의 부모를 계산한다는 것은 “가장 낮은 1 비트”를 찾아 그것을 0 으로 내리고, 그 바로 위 비트를 1 로 세우는 것과 같습니다.

이는 곧, 점 x 를 포함하는 구간들을 찾는 질의를 다음처럼 구현할 수 있음을 뜻합니다:

let m = x;
while m != M / 2 {
    // 중심이 `m`인 것으로 가정하고 `nodes[m]`에 저장된 구간을 거른다
    m = (m & (m - 1)) | (2 << m.trailing_zeros());
}

트리를 구축하려면 중심이 [l;r) 안에 있는 “가장 높은” 노드를 찾아야 합니다. 즉, 가능한 한 많은 후행 0 을 갖는 m 을 찾아 l≤m<r 를 만족시켜야 합니다. 이는 m=r−1 에서 시작해 m≥l 인 동안 바닥 비트들을 0 으로 지워 나가는 것으로 구현할 수 있습니다. 하지만 같은 일을 상수 시간에 하는 방법이 있습니다.

l−1 과 r−1 의 비트를 생각해 봅시다. 위쪽 몇 개 비트(접두사 p)가 같고, 어떤 위치 i 에서 l−1 은 0, r−1 은 1 일 수 있습니다. 이때 m=p 100…00 이면 됩니다. l−1 < m 인 것은 p 가 같고 그 다음 비트가 m 쪽이 더 크기 때문이며, m ≤ r−1 도 성립합니다(p 1 이 공통 접두사이고, 그 뒤 0 은 무엇보다 작거나 같기 때문). 그러니 m 은 유효한 선택입니다. 더구나 최적이기도 합니다. 비트 i 를 0 으로 내리면 m′=p 000…00 ≤ l−1 < l 이 보장되어 버리기 때문입니다.

삽입 코드의 결과는 다음과 같습니다:

let m = (r - 1) & (usize::MAX << ((l - 1) ^ (r - 1)).ilog2());
nodes[m].add(l, r);

단서가 하나 있습니다. 위 수식은 각각 m=0, l=0 또는 r=1 인 경우 잘 동작하지 않습니다. 몇 가지 가정이 깨지기 때문입니다. 다행히 깔끔한 해결책이 있습니다. 노드 인덱스를 계산할 때 각 좌표에 1 을 암묵적으로 더하면, 약간의 수정만으로 모든 입력에서 잘 동작하며, 심지어 코드가 더 단순해집니다:

let m = x;
while m != M / 2 - 1 {
    // 중심이 `m`인 것으로 가정하고 `nodes[m + 1]`에 저장된 구간을 거른다
    m = (m | (m + 1)) & !(2 << m.trailing_ones());
}

let m = r & (usize::MAX << (l ^ r).ilog2());
nodes[m].add(l, r);

여기서 노드 0 은 결코 접근되지 않는다는 점을 깨달았으니, 모든 노드를 1 만큼 시프트해 +1 장난질을 약간 걷어낼 수 있습니다:

let m = x;
while m != M / 2 - 1 {
    // 중심이 `m`인 것으로 가정하고 `nodes[m]`에 저장된 구간을 거른다
    m = (m | (m + 1)) & !(2 << m.trailing_ones());
}

let m = (r & (usize::MAX << (l ^ r).ilog2())) - 1;
nodes[m].add(l, r);

마지막 한 가지 요령: 트리 레이아웃이 올바로 동작하려면 크기를 다음 2의 거듭제곱으로 올림해야 하지만, 그렇다고 M=2^k 개의 모든 노드가 비어 있지 않다는 뜻은 아닙니다. 모든 좌표가 M′ 이하라면, 인덱스가 M′ 이상인 노드는 비어 있음이 보장되므로 저장하지 않아도 됩니다. 즉, 좌표 개수만큼의 노드만 있으면 됩니다. 단, 범위를 벗어난 노드가 “접근”될 수는 있지만, 채워지지는 않습니다.

제 구현은 GitHub에서 보실 수 있습니다.

아직 최적화가 별로 안 되어 있습니다. 여러 Vec을 하나의 할당으로 합치고, 정렬은 두 번만 하거나 아예 건너뛰고, 순회 로직도 더 다듬을 수 있습니다. 하지만 레이아웃 자체는 갖춰져 있습니다. 벤치마킹은 독자에게 맡기겠습니다. 멋진 추가 작업이겠지만, 하루는 24시간뿐이니까요.

이건 재미로 연구한 것입니다. 제 시나리오의 현실 데이터에서는 병목이 아니며, 최악의 경우에도 예측 가능하게 스케일하는 “적당히 빠른” 구현만 있으면 충분하거든요. 보통 미시적 최적화에 몰두하는 것과 달리, 중대형 데이터에 초점을 맞추니 상쾌합니다. 실력이 녹슬지 않도록 도와주기도 하고요.

전체적으로 볼 때, 이처럼 자료구조를 혼합한 접근은 잘 알려져 있지 않은 듯합니다. 적어도 제가 찾아보지 못했습니다. 비슷한 내용을 다룬 논문을 찾으시면 꼭 알려 주세요! 그때까지 안녕히, 여러분의 프로젝트에 행운을 빕니다.