세그먼트 트리

세그먼트 트리주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해 낸 자료구조더 큰 범위로는 '인덱스 트리'라고 불리는데, 코딩 테스트 영역에서는 큰 차이가 없다. 세그먼트 트리 핵심 이론세그먼트 트리의 종류는 구간 합, 최대/최소 구하기로 나눌 수 있고다.구현 단계는 트리 초기화하기 -> 질의값 구하기(구간 합 or 최대/최소) -> 데이터 업데이트하기  세그먼트 트리는 이론이 길었다.. 휴그래도 쓰고, 그림그려보면서 이해해보니 주어진 데이터를 세그먼트 트리로 표현하고, 인덱스 조작을 잘 하면서 노드 값을 컨트롤하면 원하는 구간 합이나, 구간의 최대 최소를 빠른 시간 복잡도로 구할 수 있는 알고리즘이다. 문제를 풀어보면서 더 이해해보자. 백준 2042번 : 구간 합 구하기https:..

2025.01.28