세그먼트 트리
-
세그먼트 트리(Segment Tree)Algorithm 2022. 5. 2. 15:49
세그먼트 트리(Segment Tree)란? 특정 구간 내 데이터에 대한 연산(쿼리)을 빠르게 구할 수 있는 트리 를 말한다. 기본적으로 세그먼트 트리를 이진 트리 구조를 가진다. 구간합을 빠르게 구하기 위해 세그먼트 트리를 사용하고자 한다면, 리프 노드에 주어진 노드 값을 저장하고, 부모 노드부터 루트 노드까지 자식 노드의 합을 저장하여 세그먼트 트리를 구성할 수 있다. → 다음 코드를 참고하자 세그먼트 트리의 장점은 구간 데이터에 대한 연산을 빠르게 할 수 있다는 것이다. 기본적으로 구간 내의 데이터를 모두 조회하여 계산하는 O(N)보다 더 빠르다. (아래 시간복잡도 참고) 시간복잡도 데이터 변경: O(logN) 연산: O(logN) 데이터 변경할때마다 M번 연산: O((logN +logN)*M) = ..