세그먼트 트리(Segment Tree)
·
PS/Algorithm
트리(Tree) 자료구조는 데이터간 위계가 있어 다양한 처리가 가능하다. 세그먼트 트리는 약간의 메모리를 할애해 구간의 값을 따로 관리하여 빠르게 구간 해를 얻도록 하는 트리이다. 세그먼트 트리는 데이터 전체 구간을 반복적으로 이분해 정복하여 구간에서 원하는 값을 저장해 빠르게 얻도록 한다. 원하는 값이라고 한다면 "구간의 합, 곱", "구간 내 최대, 최소 값" 등이 가능하고 분할 정복으로 구간의 해를 얻을 수 있는 문제라면 세그먼트 트리를 적용할 수 있다. 세그먼트 트리는 데이터 접근에서 정확도가 요구되기 때문에 처음에는 구현하기가 매우 까다롭다.(진짜 개고생했다.) 우선 이 글에서는 새로운 데이터를 추가하지 않는 조건에서 세그먼트 트리를 만들고 원하는 구간 해를 출력하는 쿼리를 구현해본다. 1. 트..