코딩못하는사람

세그먼트 트리란? 세그먼트 트리(Segment Tree) 또는 인덱스 트리(Index Tree)는 다음 두 연산을 어떻게 더 효율적으로 할까에 대한 고민에서 출발한다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 i번째 수를 v로 바꾸기. A[i] = v 두번째 연산은 O(1)에 해결할 수 있겠지만 첫 번째 연산은 l-r의 길이만큼의 시간 O(NM)이 쿼리가 요청될 때 마다 소요될 것이다. (쿼리 m번 구간크기 n) 따라서 우리는 M과 N이 클때를 위한 자료구조인 세그먼트 트리를 알아야한다. 가장 기본적인 2,3,7,4,5,9,6,1의 구간합을 구하는 세그먼트 트리를 보자. 트리는 완전 이진 트리로 구성된다. 또한 트리의 ..