세그먼트 트리 (Segment Tree)
쉽게 풀면
1000개의 숫자가 있을 때 "10번째부터 500번째까지의 합은?"이라는 질문에 매번 490개를 하나씩 더하면 느립니다. 세그먼트 트리는 마치 회사 조직도처럼, 전체를 큰 팀으로 나누고 그 팀을 다시 작은 팀으로 계속 쪼개어 각 팀(구간)의 합계를 미리 계산해 둡니다. 그러면 어떤 구간에 대한 질문이 와도 몇 개의 팀 합계만 조합하면 되고, 특정 값이 바뀌어도 그 값이 속한 팀들의 합계만 위로 갱신하면 되어 빠릅니다.
왜 중요한가
구간 질의와 값 갱신이 동시에 빈번히 일어나는 문제는 컴퓨터과학 전반에서 흔하기 때문에, 세그먼트 트리는 알고리즘 설계뿐 아니라 데이터베이스 인덱싱, 계산기하학, 경쟁 프로그래밍 등 다양한 응용 논문에서 기본 자료구조로 반복해서 등장합니다. 특히 데이터가 계속 갱신되는 스트리밍 환경에서 효율을 보장해야 하는 시스템 논문에서 성능 개선의 근거로 자주 인용됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 데이터가 계속 바뀌는 상황에서도 "이 구간의 최댓값은?" 같은 질의에 매번 전체를 훑지 않고 로그 시간 안에 답할 수 있도록 세그먼트 트리 구조를 사용했다는 뜻입니다. 알고리즘·데이터베이스·실시간 시스템 분야 논문에서 자주 등장합니다.
계산기하학 논문에서는 좌표를 구간으로 취급해 도형들의 겹침이나 교차 영역을 효율적으로 계산하는 데 세그먼트 트리가 핵심 자료구조로 쓰입니다.
데이터베이스 시스템 논문에서는 구간 집계 질의의 응답 속도를 개선하는 인덱싱 기법의 하나로 세그먼트 트리를 소개하고 성능을 비교하는 경우가 많습니다.
조금 더 깊게 보면
세그먼트 트리는 기본형 외에도 여러 변형이 있는데, 갱신을 특정 값 하나가 아니라 구간 전체에 한 번에 적용해야 할 때는 지연 전파(lazy propagation) 기법을 함께 사용해 갱신 연산도 로그 시간에 처리합니다. 또한 값이 좌표처럼 매우 큰 범위에 흩어져 있을 때는 필요한 노드만 그때그때 생성하는 동적 세그먼트 트리(dynamic segment tree)나, 시간 축을 추가로 얹은 지속성 세그먼트 트리(persistent segment tree) 같은 변형도 연구에서 활용됩니다.
주의할 점
세그먼트 트리는 펜윅 트리와 자주 비교되는데, 펜윅 트리는 구현이 더 간단하고 메모리를 적게 쓰지만 구간 합처럼 비교적 단순한 연산에 적합한 반면, 세그먼트 트리는 최댓값·최솟값 등 더 다양한 질의와 구간 갱신까지 유연하게 지원할 수 있다는 차이가 있습니다.