1. 세그먼트 트리 및 응용

• *세그먼트 트리(Segment Tree)**는 배열의 구간 쿼리(부분 범위의 합, 최솟값, 최댓값 등)를 빠르게 처리하기 위한 자료구조입니다. 배열을 여러 구간으로 나누어 각 구간의 정보를 저장하고, 이를 바탕으로 원하는 구간의 값을 빠르게 계산할 수 있습니다.
• 구조: 세그먼트 트리는 이진 트리 구조로, 리프 노드에는 배열의 개별 원소 값이 저장되고, 상위 노드에는 구간 값(구간 합, 구간 최소/최대 등)이 저장됩니다.
• 구간 쿼리: 특정 구간에 대한 값을 빠르게 구할 수 있습니다. 예를 들어, 배열의 특정 범위 [L, R]에 대한 합을 O(log n) 시간에 구할 수 있습니다.
• 업데이트: 배열의 특정 원소 값을 변경할 때, 관련된 트리 노드를 업데이트하여 구간 값도 반영할 수 있습니다.

세그먼트 트리의 응용:

1. 구간 합 쿼리: 배열의 특정 구간 합을 빠르게 구합니다.
2. 구간 최소/최댓값 쿼리: 특정 구간에서의 최소값이나 최댓값을 빠르게 구합니다.
3. 구간 업데이트: 특정 범위의 값을 일괄적으로 변경하는 경우에도 적용 가능합니다(예: lazy propagation 기법을 사용).

세그먼트 트리 객관식 문제:

Q. 세그먼트 트리의 각 노드가 저장하는 값으로 적합하지 않은 것은 무엇인가?

1. 배열의 구간 합
2. 배열의 구간 곱
3. 배열의 구간 최솟값
4. 배열의 구간 정렬

정답: 4. 배열의 구간 정렬

(세그먼트 트리는 특정 구간의 값(합, 최소/최댓값 등)을 저장하지만, 구간 내 값을 정렬하는 것은 처리하지 않습니다.)

시간 복잡도

1. 구간 쿼리: O(log n)
   • 특정 범위 [L, R]에 대한 합, 최솟값, 최댓값 등을 구하는 쿼리는 O(log n) 시간에 수행됩니다. 이는 트리의 깊이가 log n이기 때문입니다.