트리1 세그먼트 트리(Segment Tree) 세그먼트 트리는 구간의 값을 저장하는 트리입니다. 1~N인 수열이 있을 때, "인덱스가 a~b인 수들의 합을 구하고 싶다." 혹은, "a~b번째 수들 중 최소 값이나 최대값을 구하고 싶다." 같은 경우 사용합니다. 세그먼트 트리는 이진 트리 모습을 가지며 자식 노드는 부모 노드의 범위를 반 씩 가지고 있습니다. 즉, 부모 노드가 1~5까지의 구간합을 가지고 있다면 자식 노드의 왼쪽 자식은 1~3의 구간 합을 가지고 오른쪽 자식은 4~5까지의 구간 합으로 나눠가집니다. 수열의 크기(N)가 5인 수열 A = {1, 2, 3, 4, 5}의 구간 합을 구하고자 할 때 사용하는 세그먼트 트리를 생성해 봅시다. 인덱스(i)는 접근이 쉽게 0이 아닌 1부터 시작하였습니다. 처음 상태의 세그먼트 트리는 다음과 같습니다.. 2020. 2. 2. 이전 1 다음
