세그먼트 트리(Segment Tree) 배열 간격에 대한 정보를 이진 트리에 저장하는 자료구조 여러 개의 데이터가 존재할 때 특정 구간의 합(최솟값, 최댓값, 곱 등)을 구하는 데 사용하는 자료구조 세그먼트 트리의 특징 이진 트리 기반 각 노드는 left, right 노드 두 개만의 자식을 가질 수 있음 구간 정보 저장 각 노드는 자신이 나타내는 구간의 정보를 저장 배열에서 특정 구간의 합을 구하는 방법 배열을 이용하여 선형적으로 구하기 트리 구조를 이용하여 구하기 배열을 이용하여 선형적으로 구하기 배열 A 배열 A에서 Index 2 .. 8 까지의 합 구하기 트리 구조를 이용하여 구하기 트리 A 이러한 세그먼트 트리가 존재할 경우 구간 합을 구하는 시간은 O(logn) 세그먼트 트리 구현 구간 합 저장..
