Computer Science/Algorithm
[Algorithm] 세그먼트 트리(Segment Tree)에 대해서 알아보자
세그먼트 트리(Segment Tree)란 세그먼트 트리(Segment Tree)는 효율적으로 배열 또는 리스트와 같은 순차적인 데이터 구조에서 구간 쿼리(구간 검색 또는 구간 연산)를 수행하기 위한 자료구조입니다. 주로 구간 합, 구간 최솟값, 구간 최댓 값 등을 빠르게 계산하는데 사용됩니다. 세그먼트 트리는 트리 구조로 표현되며, 각 노드는 배열의 일부 구간에 대한 정보를 저장합니다. 일반적으로 이진 트리 형태를 가지며, 아래와 같은 구성요소를 가집니다. 루트 노드 : 배열 전체 구간에 대한 정보를 저장합니다. 각 내부 노드 : 두 자식 노드의 구간 정보를 합친 결과를 저장합니다. 이를 통해 트리를 아래로 내려가면서 구간 정보를 계산할 수 있습니다. 리프 노드 : 배열의 개별 원소를 나타냅니다. 세그먼..
