Search

세그먼트 트리

세그먼트 트리는 배열의 값들을 구간별로 나누어, 해당 구간의 구간합 혹은 최대/최소를 트리에 저장하는 방식이다.
이와 같이 값들이 저장된 배열을 아래처럼 각 이진트리의 노드별로 구간을 반씩 나누고 해당 구간의 구간합을 저장한다.