세그먼트 트리
-
백준 2042 구간 합 구하기Algorithm/BOJ 2021. 4. 8. 13:50
출처: www.acmicpc.net/problem/2042 분류: 세그먼트 트리, 구간 합 접근방식 세그먼트 트리의 예제 같은 문제입니다. 세그먼트 트리를 공부했다면 쉽게 풀 수 있었습니다. 세그먼트 트리가 궁금하시다면 여기로 :) 해결방법 class SegmentTree { var value: T var function: (T, T) -> T var leftBounds: Int var rightBounds: Int var leftChild: SegmentTree? var rightChild: SegmentTree? init(array: [T], leftBounds: Int, rightBounds: Int, function: @escaping (T, T) -> T) { self.leftBounds = l..
-
SegmentTreeAlgorithm/Theory 2021. 4. 8. 13:47
구간별로 특정한 결과 값을 관리할 때 사용하는 자료구조. 이진트리로 재귀적 구현이 특징. - query (특정 구간의 결과) O(logN) - replace (특정 인덱스 교체) O(logN) 안녕하세요 :) 오늘은 SegementTree에 대해 알아보려고 합니다. 먼저 SegemetTree 는 언제, 왜 사용할까요? SegemtTree 라는 이름이 나타내듯이 구간별로 특정한 결과값을 관리하고 싶을 때 사용하는 자료구조 입니다. 주로 구간 합을 구할 때 많이 사용하죠! 세그먼트 트리는 이진트리로 leaf 노드가 해당 인덱스의 값을 가지고 있습니다. 아래 그림처럼 전체 구간부터 반씩 잘라서 구간을 나눠 놓은 자료구조에요! 세그먼트 트리의 핵심은 재귀적 반복에 있습니다. 생각보다 어렵지 않아요 :) Sege..