세그먼트 트리 시각화
구간 합·최솟값 등 범위 쿼리를 O(log n)으로 처리하는 트리를 단계별로 학습하세요
자료구조★★☆
속도
1 / 1배열: [5, 8, 6, 3, 2, 7, 4, 1]쿼리 타입: sum
연산 선택
쿼리 타입
현재구간 일치방문건너뜀업데이트
세그먼트 트리의 빌드·쿼리·업데이트 과정을 단계별로 관찰하세요.
연산을 선택하고 실행을 눌러 시작하세요.
세그먼트 트리란?
배열의 구간 정보(합, 최솟값 등)를 트리 형태로 저장하여 구간 쿼리와 점 업데이트를 모두 O(log n)에 처리하는 자료구조입니다.
사용 방법
- 1배열을 입력하고 빌드하면 세그먼트 트리가 생성됩니다
- 2구간 범위를 지정하여 합/최소/최대 쿼리를 실행하세요
- 3특정 인덱스의 값을 변경하면 트리가 업데이트됩니다
- 4쿼리 타입을 변경하여 다른 연산을 실험해보세요
동작 원리
- 1리프 노드는 원본 배열의 각 원소를 저장합니다
- 2내부 노드는 자식 구간의 합/최솟값을 저장합니다
- 3쿼리 시 구간에 해당하는 노드만 방문하여 O(log n)에 답을 구합니다
- 4업데이트 시 해당 리프부터 루트까지의 경로만 갱신합니다
실무 활용
- •경쟁 프로그래밍(CP)의 구간 쿼리 문제 해결
- •데이터베이스의 범위 집계(OLAP) 쿼리 최적화
- •이미지 처리의 2D 구간 합(Summed Area Table)
- •게임 서버의 실시간 랭킹 시스템
비슷한 알고리즘
- •펜윅 트리(BIT) — 구현이 간단하고 메모리 효율적이나 구간 최솟값 등 일부 연산 불가
- •스파스 테이블 — O(1) 쿼리가 가능하나 업데이트 불가(정적 배열 전용)
- •sqrt 분할 — 구현이 단순하나 O(√n) 쿼리로 느림
학습 팁
- •작은 배열(4~8개)부터 시작하여 트리 구조를 파악하세요
- •쿼리 시 어떤 노드가 방문되는지 하이라이트를 관찰하세요
- •lazy propagation 확장을 위한 기초로 활용하세요
자주 묻는 질문
Q. 펜윅 트리와 어떤 차이?
A. 세그먼트 트리가 더 범용적(최솟값 등 지원)이고, 펜윅은 합 쿼리에 특화되어 더 간결합니다.
Q. 메모리 사용량은?
A. 배열 크기 n에 대해 약 4n 공간이 필요합니다.