[자료구조] 세그먼트 트리에 대해 설명해주세요.

💡여러 개의 데이터가 존재할 때 특정 구간의 합(최솟값, 최댓값, 곱 등)을 구하는 데 사용하는 자료구조이다. 트리 종류 중에 하나로 이진 트리의 형태이며, 특정 구간의 합을 가장 빠르게 구할 수 있다는 장점이 있다. (O(logN))

이때, 세그먼트 트리의 인덱스가 1부터 시작하는 이유는 재귀적으로 편하게 세그먼트 트리를 다루기 위해서 이다.
2 * idx => 왼쪽 노드 가리킴
2 * idx + 1 => 오른쪽 노드 가리킴

(출처: https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%AC-Segment-Tree)

특정 노드의 수가 수정될 때, 해당 노드가 범위 안에 있는 있는 경우에 한하여 수정을 진행해주면 된다. O(log(N))

관련 문제

https://www.acmicpc.net/step/35

Reference

• [자료구조] 세그먼트 트리 (Segment Tree)