세그먼트 트리
세그먼트 트리은 배열의 구간 합·최솟값 같은 결합 가능한 연산을 트리 노드에 집약해 빠르게 조회·수정한다 구간 질의 자료구조 분야의 대표적인 기술로, 데이터의 표현과 입력 조건에 맞는 계산 절차를 정의한다. 적용 목적이 유사한 다른 방법과 비교할 때 정확성 보장과 결과의 해석이 중요하다...
| 분류 | 알고리즘 · 구간 질의 자료구조 |
|---|---|
| 주요 목적 | 배열의 구간 합·최솟값 같은 결합 가능한 연산을 트리 노드에 집약해 빠르게 조회·수정한다 |
| 핵심 방법 | 이진 트리의 각 노드에 구간의 결과를 저장하고 질의 범위가 노드 구간을 덮으면 저장된 값을 이용한다 |
| 복잡도 | 구축 O(n), 구간 질의·점 갱신 O(log n), 공간 O(n) |
| 적용 조건 | 집약 연산의 결합법칙과 항등원, 갱신이 결합 연산에 미치는 영향을 정의해야 한다 |
| 참고 자료 | 기술 자료 |
| 관련 분야 | 자료구조, 계산 복잡도 |
세그먼트 트리은 배열의 구간 합·최솟값 같은 결합 가능한 연산을 트리 노드에 집약해 빠르게 조회·수정한다 구간 질의 자료구조 분야의 대표적인 기술로, 데이터의 표현과 입력 조건에 맞는 계산 절차를 정의한다. 적용 목적이 유사한 다른 방법과 비교할 때 정확성 보장과 결과의 해석이 중요하다.[1]
핵심 작동은 다음과 같다. 이진 트리의 각 노드에 구간의 결과를 저장하고 질의 범위가 노드 구간을 덮으면 저장된 값을 이용한다. 점 갱신은 루트 방향으로 재계산하며 구간 갱신은 지연 전파를 사용할 수 있다. 이 절차에서 각 단계에 유지되는 값의 의미를 정의하고 자료구조 또는 수치 표현에 따라 처리 순서를 구현한다.
계산 특성은 구축 O(n), 구간 질의·점 갱신 O(log n), 공간 O(n) 실제 구현에는 집약 연산의 결합법칙과 항등원, 갱신이 결합 연산에 미치는 영향을 정의해야 한다 단계마다 유지되어야 하는 불변식, 종료 조건과 입력 경계를 검사하면 수학적 모델을 프로그램의 동작과 연결할 수 있다.
활용과 다른 기법과의 관계에서는 경쟁 프로그래밍·시계열 질의·온라인 배열 갱신에 사용한다. 펜윅 트리는 합과 역연산 등 특정 구조에서 더 간단하다. 실제 시스템에서는 시간·메모리 사용, 입출력 비용, 정밀도와 저장 형식이 성능에 영향을 줄 수 있다. 필요한 경우 가장 작은 입력과 중복·퇴화 상태도 시험해야 한다.[2]