세그먼트 트리 (Segment Tree)

아래 블로그를 참고해 정리했습니다.

https://m.blog.naver.com/ndb796/221282210534

41. 세그먼트 트리(Segment Tree)

 

 

 

세그먼트 트리의 아이디어

범위를 반으로 나누어서 왼쪽 반의 합은 이진트리의 왼쪽 자식에, 

오른쪽 반의 합은 이진트리의 오른쪽 자식에 저장하는 것이다. 

 

결국 세그먼트 트리의 각 노드에는 모든 범위의 합이 저장되고, 이진트리이므로 탐색은 O(logN)에 끝낼수 있다. 

즉 미리 데이터를 가공해 트리를 만들어 놓고 구간합이 필요하면 O(N)이 아닌 O(logN)에 구간합을 구할수 있게 된다. 

 

 

세그먼트 트리 생성 시간복잡도

생성할때는 결국 모든 노드들을 한번씩 방문하게 되므로 O(N) 이다.

그런데 N이 기존 배열의 N은 아니고 최종적으로 만들어지는 세그먼트 트리의 노드의 갯수다. 

 

세그먼트 트리에서 구간합 구하기 , 수정 시간복잡도

세그먼트 트리는 이진 트리이므로 높이 logN을 갖는다.

따라서 탐색 시간 복잡도는 O(logN).