# Segment Tree :face_with_monocle:
- Segment tree는 구간합이나 곱 등 **구간의 대푯값을 tree 구조를 활용하여 구하는 자료구조**다.
- 특정 위치에 있는 값이 업데이트 되었을 때도 다시 $O(N)$ 시간을 소요하며 계산할 필요없이 $O(logN)$ 의 시간으로 계산할 수 있다는 장점이 있다.
- Segment tree의 크기는 미리 할당할 수 있는 아이템의 개수 $N$과 가장 가까운 제곱수 ($N$이 10일 경우 $2^4$가 가장 가까운 수임)에 2를 곱한 값 (32)이라고 함.

활용 사례
---
- 특정 구간의 합/최댓값/최솟값 구하기