tree

세그먼트 트리 (Segment Tree)

세그먼트 트리는 "구간을 저장하기 위한 트리" 이다. 예를 들어서 int Array[5] = { 1, 2, 3, 4, 5 } 2번째 값 부터 4번째 값 까지의 합은 2 + 3 + 4로 계산할 것이며 1번째 값 부터 5번째 값 까지의 합은 1 + 2 + 3 + 4 + 5로 계산하게 될 것이다. 특정 구간에 대한 연산이라면, 모든 합을 다 구해놓고 계산하는 방식을 생각할 수 있다. 이걸 1번 연산 이라고 칭하자. 2번 째 값을 7로 바꾸면 { 1, 7, 3, 4, 5 }. 이렇게, 특정 값을 바꾸는 연산 2번 연산 이라고 칭하자. 이 후에 2번째 값부터 4번째 값 까지의 합을 구하고 3번째 값부터 5번째 값 까지의 합을 구하고, 4번째 값을 6으로 바꾸는거와 같은 연산들이 쭉 이어진다고 생각해보자. 별로 문..