세그먼트 트리 설명 및 백준 2042번 문제 풀이 https://chb2005.tistory.com/83 [JAVA] 세그먼트 트리 (Segment Tree) Segment Tree 란? 데이터 집합이 주어지고, 특정 구간의 합, 최대, 최소 값을 구해야하는 문제가 주어짐 이 때, 구간이 여러개이거나 데이터가 업데이트 될 수 있는 상황에서 더 빠르게 찾아내기 위 chb2005.tistory.com

Segment Tree 란? 데이터 집합이 주어지고, 특정 구간의 합, 최대, 최소 값을 구해야하는 문제가 주어짐 이 때, 구간이 여러개이거나 데이터가 업데이트 될 수 있는 상황에서 더 빠르게 찾아내기 위해 고안된 자료구조 Sement Tree 사용 예제 입력으로 5, 2, 4, 3, 1이 들어왔다고 가정 + 업데이트를 반영한 구간합을 출력해야 되는 상황 트리 초기화 입력으로 들어온 5개의 데이터를 모두 리프 노드에 넣어야 됨 리프노드 : 자식이 없는 노드 이런 식의 트리로 만드는게 목표 배열 사용 (루트 노드가 1번, 1번의 자식들이 순서대로 2, 3번, .... index가 8인 위치에 5를 넣어줌, .....) arr[1~15] = [0, 0, 0, 0, 0, 0, 0, 5, 2, 4, 3, 1, ..