세그먼트 트리 (구간 트리, Segment Tree)

☞ 세그먼트 트리란 이름 그대로 저장된 자료를 적절히 구간별로 전처리해 그들에 대한 질의들을 빠르게 대답할 수 있도록 해주는 트리입니다. 예를 들어 A={1,2,3,4,5}에서 [2,4] 구간의 최소치를 알고 싶다면 해당 배열을 순회하며 찾는 방법도 있지만, 해당 배열을 전처리해 세그먼트 트리를 생성해 더욱 더 빠르게 구현 할 수 있습니다. A배열을 세그먼트 트리로 바꾼 후 -> 아래처럼 구간별로 나눠 세그먼트 트리를 만들 수 있다. ☞ 이렇게 이론적으로만 설명했지만, 코드 구현에 많은 어려움이 있을 수 있습니다. 그래서 세그먼트 트리 문제의 한 유형인 구간 최소 쿼리(range minimum query,RMQ)를 구현해보겠습니다. ※ 여기서 중요한 점은 세그먼트 트리에 초기 크기를 설정해줘야하는데 가장..