배열이나 리스트 내부의 '특정 구간에 대한 합(Sum)'을 구하거나, '특정 인덱스의 값을 빈번하게 변경'해야 하는 상황은 코딩 테스트의 고난도 문제나 실무 대규모 시스템 성능 최적화에서 매우 흔하게 발생합니다. 만약 100만 개의 데이터가 있는 배열에서 "10만 번째부터 90만 번째까지의 합을 구하라"는 쿼리가 10만 번 들어온다면 어떻게 될까요? 단순 반복문(for문)을 쓰면 매번 O(N)의 시간이 걸려 전체 시스템이 다운될 것입니다. 그렇다고 누적 합(Prefix Sum) 배열을 미리 만들어 쓰자니, 배열 안의 데이터가 단 하나라도 변경될 때마다 전체 누적 합 배열을 100만 번 다시 계산해야 하는 치명적인 단점이 존재합니다. 이처럼 '빈번한 데이터의 수정'과 '거대한 구간에 대한 쿼리(합, 최댓값, 최솟값)'라는 두 마리 토끼를 모두 잡아야 할 때 등장하는 구세주가 바로 세그먼트 트리(Segment Tree)입니다. 오늘 이 글에서는 구간 쿼리계의 마스터키인 세그먼트 트리의 완벽한 구조와 O(log N) 동작 원리를 샅샅이 파헤쳐 보겠습니다.
1. 세그먼트 트리(Segment Tree)란 무엇인가?
세그먼트 트리는 이름 그대로 여러 개의 데이터 구간(Segment)에 대한 다양한 통계 정보(구간 합, 최솟값, 최댓값, 최대공약수 등)를 트리의 각 노드에 분할하여 저장하는 매우 영리한 이진 트리(Binary Tree) 자료구조입니다.
1-1. 이진 트리 구조의 매핑 원리
원본 데이터 배열 [5, 8, 4, 3]이 있다고 가정해 봅시다. 세그먼트 트리는 이 데이터를 바탕으로 아래에서부터 위로 다음과 같은 계층을 쌓아 올립니다.
- 리프 노드 (Leaf Node): 트리의 맨 밑바닥에는 원본 배열의 개별 데이터들이 하나씩 고스란히 들어갑니다. (5, 8, 4, 3)
- 내부 노드 (Internal Node): 부모 노드는 자신의 두 자식 노드가 가진 값의 '합(Sum)'을 계산하여 저장합니다. 즉, 5와 8의 부모는 13을, 4와 3의 부모는 7을 가집니다. 이 값은 각각 특정 구간의 누적 합을 의미합니다.
- 루트 노드 (Root Node): 트리의 최상단에는 13과 7의 합인 20, 즉 전체 배열(인덱스 0부터 3까지)의 총합이 최종적으로 저장됩니다.
이러한 피라미드식 계층 구조를 미리 구축해 두면, 거대한 구간의 합을 구할 때 밑바닥 리프 노드까지 하나하나 내려가서 일일이 더할 필요 없이, 이미 중간에 계산되어 있는 부모 노드의 큼지막한 구간 합 덩어리들을 쏙쏙 골라 더하기만 하면 끝이 납니다.
2. 세그먼트 트리의 두 가지 핵심 마법 (O(log N))
세그먼트 트리는 꽉 찬 형태에 가까운 이진 트리의 형태를 완벽하게 띠고 있기 때문에, 트리의 전체 높이는 $\log_2 N$에 수렴합니다. 이 높이 덕분에 삽입과 조회 모두 경이로운 속도를 냅니다.
2-1. 데이터 변경 (Update) 로직
만약 배열의 세 번째 값인 4를 9로 바꾸고 싶다면 어떻게 해야 할까요?
세그먼트 트리에서는 리프 노드에 있는 4를 9로 바꾼 뒤, 그 노드와 직계로 연결된 부모 노드들을 타고 루트 노드까지 위로 쭉 거슬러 올라가며 합을 다시 갱신해 주기만 하면 됩니다. 변경된 값이 속하지 않은 다른 구간의 노드들은 전혀 건드릴 필요가 없습니다. 트리의 높이만큼만 위로 올라가면 되므로, 데이터 100만 개 중 하나를 바꾼 뒤 전체 구간 합 정보를 최신화하는 데 걸리는 시간은 고작 O(log N) (약 20번 내외의 연산)밖에 걸리지 않습니다. 누적 합(Prefix Sum)이 O(N)으로 100만 번을 다시 계산해야 했던 것과 비교하면 엄청난 발전입니다.
2-2. 구간 합 구하기 (Query) 로직
사용자로부터 특정 구간의 합을 요청받았을 때, 노드가 현재 담당하고 있는 구간과 요청받은 구간을 겹쳐보며 매우 영리하게 분할 정복 탐색을 진행합니다.
- 요청 구간이 현재 노드의 구간을 완벽히 포함(Cover)한다면: 더 아래로 탐색을 진행할 필요 없이, 현재 노드가 들고 있는 덩어리 합계 값을 그대로 즉시 반환합니다.
- 요청 구간이 현재 노드의 구간과 단 1%도 겹치지 않는다면: 이 구간은 정답과 무관하므로 탐색을 즉시 종료하고 0을 반환합니다.
- 구간이 애매하게 일부만 겹친다면: 현재 노드의 구간을 반으로 갈라, 왼쪽 자식과 오른쪽 자식으로 탐색을 재귀적으로 쪼개어 내려갑니다.
이 영리한 분할 정복 탐색 로직 덕분에 아무리 넓고 방대한 구간의 합을 구하더라도 O(log N)만에 정확한 정답을 추출할 수 있습니다.
3. 배열을 이용한 세그먼트 트리의 메모리 할당 공식
세그먼트 트리는 포화 이진 트리(Full Binary Tree)의 형태에 가깝기 때문에, 복잡하게 좌우 포인터를 가진 객체(Node)를 만들지 않고 1차원 배열(Array)만으로 깔끔하게 메모리에 구현합니다.
이때 배열의 크기를 얼마나 넉넉하게 잡아야 할지가 초보자들에게 가장 큰 고민거리입니다. 수학적으로 증명된 가장 안전한 메모리 할당 공식은 "원본 배열 크기(N)의 4배"를 할당하는 것입니다.
// N개의 데이터를 담기 위한 세그먼트 트리 배열의 런타임 에러 방지용 안전 크기 할당 (Java)
int[] tree = new int[N * 4];
물론 수학적으로 정확하게는 트리의 높이 $H = \lceil \log_2 N \rceil$를 구한 뒤 $2^{H+1}$ 크기를 할당하는 것이 메모리 바이트를 아끼는 정석이지만, 실전 코딩 테스트 현장에서는 간편하게 N * 4를 곱해버리는 것이 메모리 초과 없이 런타임 에러(Index Out of Bounds)를 완벽하게 방지하는 최고의 실전 팁입니다.
1. 세그먼트 트리(Segment Tree)는 거대한 배열의 특정 구간의 합, 최솟값, 최댓값 등을 매우 빠르게 구하고 빈번한 데이터 수정까지 완벽하게 지원하는 이진 트리 자료구조입니다.
2. 데이터의 갱신(Update)과 구간 탐색 쿼리(Query)를 모두 O(log N)의 극단적으로 빠른 속도로 처리하여 단순 누적 합(Prefix Sum)의 한계를 완벽히 극복합니다.
3. 객체 대신 접근 속도가 빠른 1차원 배열로 구현하며, 트리를 담기 위한 배열의 전체 크기는 원본 데이터 개수의 4배(4 * N)로 넉넉히 설정하는 것이 가장 안전합니다.