Tree1 [자료구조] Segment Tree(세그먼트 트리) 1. Segment Tree(세그먼트 트리) Segment Tree(세그먼트 트리)는 배열 간격에 대한 정보를 이진 트리에 저장하는 자료구조입니다. Segment Tree를 도식화하면, 아래와 같습니다. Segment Tree는 다양한 활용법이 있겠지만, 특히 특정 데이터 배열의 구간 합을 계산할 때 유용합니다. 아래 예시를 통해, 단순 배열 방법과 Segment Tree 활용법을 비교해보겠습니다. 예시 1) 단순 배열 방법 array = {1, 2, 3, ..., N} 배열에서 특정 범위의 구간 합과 특정 인덱스의 값 변경을 M번 수행 (1) array 배열에서 1번째 ~ N번째까지 구간 합 연산S = array[0] + array[1] + array[2] + ... + array[N - 1]시간 복.. 2024. 9. 12. 이전 1 다음
