Segment Tree1 [Algorithm] 세그먼트 트리 (Segment Tree) 세그먼트 트리란? 세그먼트 트리는 완전 이진 트리를 기반으로 주어진 쿼리에 빠르게 응답하기 위해 만들어진 자료구조이다. 각 노드는 구간, 혹은 그 구간의 정보(구간합, 구간의 최솟값 등에 대한)를 저장하고 있는 자료구조이다. 리프 노드들은 길이가 1인 각각의 구간을 갖고 있고 부모 노드는 자신의 자식들의 구간의 합을 갖고 있으며 모든 구간은 연속적이다. 루트는 전체 구간을 포함하게 된다. 세그먼트 트리의 시간 복잡도 -> O(logN) 세그먼트 트리는 한 번의 연산에 O(logN)의 시간복잡도를 가진다. 만약 0번부터 7번 인덱스까지의 원소의 합을 구한다고 가정해보자. 완전탐색으로 값을 구할 경우 총 7번의 연산이 필요하다. 하지만 세그먼트 트리를 사용하면 루트 노드에 0~7까지의 구간합을 갖고 있고 따.. 2022. 4. 22. 이전 1 다음
