세그먼트 트리(Segment Tree)

Overview 트리 자료구조는 데이터를 효율적으로 저장하고, 빠른 시간에 탐색, 수정 및 추가 삭제 연산을 진행할 수 있도록 도와줍니다. 구간 트리(Segment Tree)는 이 트리 구조의 이점을 살려서 특정 구간에서의 최대, 최소 값등을 빠르게 구할 수 있도록 합니다. 구간 트리는 특히 일차원 배열의 특정 구간에 대한 질문들(최대, 최소값 등)을 빠르게 대답하는 데에 주로 사용합니다. 예를 들어, 일차원 배열의 특정 구간에서 최대인 값을 찾기 위해서는 특정 구간을 일일이 순회하면서 최소값을 찾아야 했습니다. 하지만, 구간 트리를 이용하면 특정 구간의 최대값을 미리 전처리해서 부모 노드에 저장하는 방식을 취하기 때문에 (일종의 다이나믹 프로그래밍 방법이라고도 할 수 있습니다.) 훨씬 더 빠른 시간에 ..

2020.06.18