세그먼트 트리(Segment Tree)의 특징과 사용 사례에 대해 설명해주세요.

세그먼트 트리는 배열의 특정 구간에 대한 질의를 효율적으로 처리하기 위한 자료구조입니다. 기본적으로 이진 트리 형태를 가지며, 각 노드는 배열의 특정 구간에 대한 정보를 저장합니다. 예를 들어, 구간 합이나 구간 최솟값 등을 저장할 수 있습니다.

세그먼트 트리의 가장 큰 장점은 쿼리 연산의 시간 복잡도가 O(log N)으로 매우 빠르다는 점입니다. 배열의 크기가 N일 때, 트리의 높이가 log N에 비례하기 때문입니다. 또한, 특정 구간의 값을 업데이트하는 연산도 O(log N)에 수행할 수 있습니다.

주요 사용 사례로는 다음과 같은 것들이 있습니다.

• 구간 합 구하기: 배열의 특정 구간의 합을 빠르게 계산해야 할 때 유용합니다.
• 구간 최솟값/최댓값 구하기: 배열의 특정 구간에서 최솟값 또는 최댓값을 빠르게 찾아야 할 때 사용됩니다.
• Lazy Propagation: 구간 업데이트가 빈번하게 발생하는 경우, 업데이트 연산을 효율적으로 처리하기 위해 Lazy Propagation 기법을 함께 사용하기도 합니다. 이는 업데이트 정보를 노드에 저장해두었다가 필요할 때 자식 노드로 전파하는 방식입니다.