세그먼트 트리 (Segment Tree)

세그먼트 트리?

배열에 부분 합을 구할 때 사용하는 개념.
배열의 값이 지속적으로 바뀔 때 매 순간 배열의 부분 길이 만큼, 즉 O(N) 만큼의 시간이 걸리기 때문에 이를 트리로 구현하여 O(logN) 의 시간으로 해결하는 방법.

 

 

수정예정