반응형 [C++로 배우는 알고리즘과 자료구조 심화] Day 2: 세그먼트 트리 (Segment Tree) 세그먼트 트리 (Segment Tree)세그먼트 트리는 주어진 배열의 구간에 대한 정보를 효율적으로 저장하고 쿼리를 처리하기 위해 사용하는 트리 구조입니다. 세그먼트 트리는 다음과 같은 연산을 빠르게 수행할 수 있습니다:구간 합: 배열의 특정 범위에 대한 합을 구합니다.구간 최솟값/최댓값: 배열의 특정 범위에 대한 최솟값 또는 최댓값을 구합니다.구간 갱신: 배열의 특정 범위에 값을 갱신합니다.세그먼트 트리의 주요 특징시간 복잡도:빌드: (O(n))쿼리: (O(\log n))업데이트: (O(\log n))구현 방법:트리의 각 노드는 배열의 특정 구간을 나타냅니다.루트 노드는 전체 배열을 나타내고, 각 자식 노드는 배열의 절반 구간을 나타냅니다.세그먼트 트리의 기본 연산트리 빌드: 초기 배열을 기반으로 세그.. 2024. 8. 1. 이전 1 다음 반응형
