[자료구조] 세그먼트 트리 (Segment Tree)

목 차 세그먼트 트리 개념 세그먼트 트리를 하며 배운 것들 세그먼트 트리 코드 세그먼트 트리 개념 세그먼트 트리는 구간 쿼리와 업데이트를 최적으로 수행할 수 있는 유연한 자료구조이다. 주로 구간 합, 또는 구간 내 최솟값이나 최댓값을 찾는 문제에 사용된다. 기본 구조 트리 구조: 세그먼트 트리는 이진 트리 구조이며, 각 노드는 배열의 특정 구간(Segment)을 대표한다. 리프 노드: 트리 구조에서 자식 노드가 없는 노드를 말한다. 즉 트리 가장 아래에 위치한 노드들을 말한다. 내부 노드: 자식 노드들의 값을 합치거나 비교하여 해당 구간의 값을 저장한 노드들을 말한다. 작동 원리 트리 초기화: 주어진 배열로 완전 이진 트리를 만든다. O(N) SUM함수: 구간합을 구하는 함수 O(log N) UPDATE..

Algorithm 2023.11.21