Segment Tree

김펭귄·2026년 6월 1일

TIL 알고리즘

Today What I Learned (TIL)

목록 보기

141/141

1. 세그먼트 트리

Query(구간 합, 구간 최솟값 등 특정 구간에 대한 질의)와 Update(데이터 업데이트)를 가장 효율적으로 처리할 수 있는 이진 트리 자료구조

세그먼트 트리의 각 노드는 배열의 특정 구간에 대한 정보(합, 최솟값 등)를 담고 있다

루트 노드: 배열의 전체 구간 [0, N-1]의 정보
리프 노드: 배열의 실제 각 원소 ([i, i] 구간)의 값
자식 노드: 부모 노드가 [NodeStart, NodeEnd] 구간을 담당한다면,
- 왼쪽 자식은 앞쪽 절반 [NodeStart, Mid]
- 오른쪽 자식은 뒤쪽 절반 [Mid+1, NodeEnd]을 담당

원본 배열 = [1, 2, 5, 8]

Segment Tree
       [0-3] (합: 16)
       /            \
  [0-1] (합: 3)     [2-3] (합: 13)
  /       \         /       \
[0] (1)   [1] (2)  [2] (5)   [3] (8)

인덱스 1번부터 시작하는 배열로 구현하며, 데이터의 크기가 N일 때 4*N의 크기로 배열을 미리 할당

크기가 4N인 이유

\begin{aligned} &\mathbf{[1.\,\text{전제 조건: 리프 노드 개수와 트리의 높이}]} \\ &\text{원본 배열의 크기(리프 노드의 개수)를 } N\text{이라 하면, 트리의 높이 } H\text{는 다음과 같다.} \\ &H = \lceil \log_2 N \rceil \\ \\ &\text{이때, 완전 이진 트리 구조에서 인덱스 참조에 필요한 최대 노드 수(배열 크기)는 다음과 같다.} \\ &\text{Max Nodes} = 2^{H+1} - 1 = 2^{\lceil \log_2 N \rceil + 1} - 1 \\ \\ &\mathbf{[2.\,\text{상한선(Bounding) 유도 과정}]} \\ &\text{올림 기호(}\lceil \rceil\text{)의 수학적 성질인 } \lceil x \rceil < x + 1\text{ 을 이용한다.} \\ &\lceil \log_2 N \rceil < \log_2 N + 1 \\ \\ &\text{최대 노드 수 식의 지수 부분에 위 부등식을 대입한다.} \\ &2^{\lceil \log_2 N \rceil + 1} < 2^{(\log_2 N + 1) + 1} \\ &\phantom{2^{\lceil \log_2 N \rceil + 1}} = 2^{\log_2 N + 2} \\ \\ &\text{지수법칙과 로그의 성질( } 2^{\log_2 N} = N \text{ )에 의해 우변을 정리한다.} \\ &2^{\log_2 N + 2} = 2^{\log_2 N} \times 2^2 \\ &\phantom{2^{\log_2 N + 2}} = N \times 4 \\ &\phantom{2^{\log_2 N + 2}} = 4N \\ \\ &\mathbf{[3.\,\text{최종 결론}]} \\ &\text{처음 전제 식과 우변의 정리 결과를 연결하면 다음 부등식이 성립한다.} \\ &\therefore \text{Max Nodes} = 2^{\lceil \log_2 N \rceil + 1} - 1 < 4N \end{aligned}

2. 세그먼트 트리의 사용 이유

크기가 $N$ 인 배열이 있을 때, 단순 배열이나 누적 합(Prefix Sum)과 비교해 보면 세그먼트 트리의 필요성을 직관적으로 이해할 수 있다

일반 배열 : [1, 3, -2, 7]
누적 합(Prefix Sum) : [1, 4, 2, 9]

세그먼트 트리
    9
  4   5
1 3 -2 7

작업	일반 배열	누적 합 (Prefix Sum)	세그먼트 트리
특정 인덱스 값 수정 (`Update`)	$O(1)$	$O(N)$	$O(\log N)$
구간 연산 수행 (`Query`)	$O(N)$	$O(1)$	$O(\log N)$

일반 배열: 데이터 수정은 빠르지만, 구간 합을 구할 때 매번 루프를 돌면 $O(N)$ 이 걸림
누적 합 배열: 정적 데이터에서는 구간 합 $O(1)$ 로 최강이지만, 값 하나가 바뀔 때마다 뒤쪽 누적 값을 다 수정해야 하므로 $O(N)$ 이 걸림
세그먼트 트리: 값 수정과 구간 질의 모두 $O(\log N)$ 에 안정적으로 처리. 대규모 게임 서버나 실시간 데이터 통계 등 데이터가 계속 변하는 환경에서 필수적

3. 세그먼트 트리 생성 방법

세그먼트 트리는 보통 완전 이진 트리에 가깝기 때문에 포인터 구조체보다는 1차원 배열(Vector)로 구현할 때 메모리 접근 효율(Cache Hit Rate)과 구현 편의성이 좋다.
루트 노드 인덱스: 1
노드 i의 왼쪽 자식: i * 2
노드 i의 오른쪽 자식: i * 2 + 1
트리 배열의 크기는 안전하게 $4 \times N$ 크기로 할당

3.1. 트리 생성 (Build)

재귀적으로 구간을 이분 분할하며 리프 노드까지 내려간 뒤, 자식 노드들의 값을 취합하며 거꾸로 올라온다

#include <vector>

using namespace std;

// arr: 원본 배열, tree: 세그먼트 트리 (4 * N 크기)
// node: 현재 세그먼트 트리 인덱스, NodeStart~NodeEnd: 현재 노드가 커버하는 원본 배열 범위
long long Build(const vector<long long>& Arr, 
				vector<long long>& Tree, 
                int Node, int NodeStart, int NodeEnd) 
{
    // 리프 노드에 도달한 경우 원본 배열 값 저장
    if (NodeStart == NodeEnd) 
    {
        return Tree[Node] = Arr[NodeStart];
    }
    
    int Mid = (NodeStart + NodeEnd) / 2;
    // 좌우 자식 노드의 결과를 합산하여 현재 노드에 저장
    return Tree[Node] = Build(Arr, Tree, Node * 2, NodeStart, Mid) 
                      + Build(Arr, Tree, Node * 2 + 1, Mid + 1, NodeEnd);
}

3.2. 질의 (Query)

구하려는 대상 구간 [Start, End]와 현재 노드가 담당하는 구간 [NodeStart, NodeEnd]의 관계에 따라 3가지 케이스로 나뉘다.

범위를 벗어난 경우: 탐색할 필요 없음 $\rightarrow$ 0 반환 (최솟값 트리라면 INF 반환)
구간에 완전히 포함되는 경우: 현재 노드 값을 그대로 반환 (더 내려가지 않으므로 $O(\log N)$ 보장)
구간이 걸쳐 있는 경우: 좌우 자식을 모두 탐색한 뒤 결과를 합산

long long Query(const vector<long long>& Tree, 
				int Node, int NodeStart, int NodeEnd, int Start, int End)
{
	// Case 1: 범위를 완전히 벗어남
	if (Start > NodeEnd || End < NodeStart)
	{
		return 0;
	}
    // Case 2: 현재 노드의 구간이 찾고자 하는 구간에 완전히 포함됨
	if (Start <= NodeStart && NodeEnd <= End)
	{
		return Tree[Node];
	}

	// Case 3: 일부만 걸쳐 있음 -> 반으로 나눠서 재귀 탐색
	int Mid = (NodeStart + NodeEnd) / 2;
	return Query(Tree, Node * 2, NodeStart, Mid, Start, End) 
    	   + Query(Tree, Node * 2 + 1, Mid + 1, NodeEnd, Start, End);
}

3.3. 값 수정 (Update)

원본 배열의 특정 인덱스 값이 수정되면, 그 인덱스를 포함하는 노드들만 루트에서부터 수직으로 타고 내려가며 갱신. 트리의 깊이만큼만 방문하므로 $O(\log N)$

// ChangedIdx: 수정할 원본 배열의 인덱스, val: 수정값
long long Update(vector<long long>& Tree, int Node, int NodeStart, int NodeEnd, int ChangedIdx, long long Val)
{
	// 범위를 벗어나면 현재 노드의 값을 그대로 반환
	if (ChangedIdx < NodeStart || ChangedIdx > NodeEnd) return Tree[Node];

	// 리프 노드에 도달하면 새로운 값으로 갱신
	if (NodeStart == NodeEnd) return Tree[Node] = Val;

	int Mid = (NodeStart + NodeEnd) / 2;
	// 좌우 자식을 갱신한 결과의 합을 부모에게 다시 반영
	return Tree[Node] = Update(Tree, Node * 2, NodeStart, Mid, ChangedIdx, Val)
		+ Update(Tree, Node * 2 + 1, Mid + 1, NodeEnd, ChangedIdx, Val);
}

3.4. 트리 사용

int main()
{
	vector<long long> Arr = { 1, 2, 56, 4, 7, 2, 9 };
	vector<long long> Tree(Arr.size() * 4);

	Build(Arr, Tree, 1, 0, Arr.size() - 1);

	// 인덱스 2 ~ 6까지의 합
	int Sum = Query(Tree, 1, 0, Arr.size() - 1, 2, 6);
	cout << Sum << '\n';

	// Arr[2]를 6으로 수정(56 -> 6)
	Update(Tree, 1, 0, Arr.size() - 1, 2, 6);
	Sum = Query(Tree, 1, 0, Arr.size() - 1, 0, 2);
	cout << Sum << '\n';
}

4. 코테 문제

4.1. 백준 2042 구간 합 구하기

#include <iostream>
#include <vector>

using namespace std;

long long Init(vector<long long>& Tree, const vector<long long>& Arr,
	int Node, int NodeStart, int NodeEnd)
{
	if (NodeStart == NodeEnd)
	{
		return Tree[Node] = Arr[NodeStart];
	}

	int Mid = (NodeStart + NodeEnd) / 2;
	return Tree[Node] = Init(Tree, Arr, Node * 2, NodeStart, Mid)
		+ Init(Tree, Arr, Node * 2 + 1, Mid + 1, NodeEnd);
}

long long Query(const vector<long long>& Tree, int Node, int NodeStart, int NodeEnd,
	int TargetFrom, int TargetEnd)
{
	if (TargetFrom > NodeEnd || TargetEnd < NodeStart)
	{
		return 0;
	}
	if (TargetFrom <= NodeStart && NodeEnd <= TargetEnd)
	{
		return Tree[Node];
	}

	int Mid = (NodeStart + NodeEnd) / 2;
	return Query(Tree, Node * 2, NodeStart, Mid, TargetFrom, TargetEnd)
		+ Query(Tree, Node * 2 + 1, Mid + 1, NodeEnd, TargetFrom, TargetEnd);
}

long long Update(vector<long long>& Tree, int Node, int NodeStart, int NodeEnd, 
	int ChangedIdx, long long Val)
{
	if (ChangedIdx < NodeStart || ChangedIdx > NodeEnd)
    {
    	return Tree[Node];
    }
	if (NodeStart == NodeEnd)
    {
    	return Tree[Node] = Val;
    }

	int Mid = (NodeStart + NodeEnd) / 2;
	return Tree[Node] = Update(Tree, Node * 2, NodeStart, Mid, ChangedIdx, Val)
		+ Update(Tree, Node * 2 + 1, Mid + 1, NodeEnd, ChangedIdx, Val);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M, K;
	cin >> N >> M >> K;
	vector<long long> Arr(N);
	for (int i = 0; i < N; i++)
	{
		cin >> Arr[i];
	}

	vector<long long> SegmentTree(4 * N);
	Init(SegmentTree, Arr, 1, 0, N - 1);

	for (int i = 0; i < M + K; i++)
	{
		long long a, b, c;
		cin >> a >> b >> c;
		if (a == 1)
		{
			Update(SegmentTree, 1, 0, N - 1, b - 1, c);
		}
		else
		{
			cout << Query(SegmentTree, 1, 0, N - 1, b - 1, c - 1) << '\n';
		}
	}
}

4.2. 백준 10868 최솟값

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

long long Init(const vector<long long>& Arr, vector<long long>& Tree, int Node,
	int NodeStart, int NodeEnd)
{
	if (NodeStart == NodeEnd)
	{
		return Tree[Node] = Arr[NodeStart];
	}

	int Mid = (NodeStart + NodeEnd) / 2;
	return Tree[Node] = min(Init(Arr, Tree, Node * 2, NodeStart, Mid),
		Init(Arr, Tree, Node * 2 + 1, Mid + 1, NodeEnd));
}

long long Query(const vector<long long>& Tree, int Node, int NodeStart, int NodeEnd,
	int TargetStart, int TargetEnd)
{
	if (TargetStart > NodeEnd || TargetEnd < NodeStart)
	{
		return numeric_limits<long long>::max();
	}
	if (TargetStart <= NodeStart && NodeEnd <= TargetEnd)
	{
		return Tree[Node];
	}

	int Mid = (NodeStart + NodeEnd) / 2;
	return min(Query(Tree, Node * 2, NodeStart, Mid, TargetStart, TargetEnd),
		Query(Tree, Node * 2 + 1, Mid + 1, NodeEnd, TargetStart, TargetEnd));
}

long long Update(vector<long long>& Tree, int Node, int NodeStart, int NodeEnd,
	int ChangedIdx, long long Value)
{
	if (ChangedIdx < NodeStart || ChangedIdx > NodeEnd)
	{
		return Tree[Node];
	}
	if (NodeStart == NodeEnd)
	{
		return Tree[Node] = Value;
	}

	int Mid = (NodeStart + NodeEnd) / 2;
	return Tree[Node] = min(Update(Tree, Node * 2, NodeStart, Mid, ChangedIdx, Value),
		Update(Tree, Node * 2 + 1, Mid + 1, NodeEnd, ChangedIdx, Value));
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M;
	cin >> N >> M;
	vector<long long> Arr(N);
	for (int i = 0; i < N; i++)
	{
		cin >> Arr[i];
	}

	vector<long long> SegmentTree(4 * N);
	Init(Arr, SegmentTree, 1, 0, N - 1);

	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		cout << Query(SegmentTree, 1, 0, N - 1, a - 1, b - 1) << '\n';
	}
}

김펭귄

반갑습니다

이전 포스트