세그먼트 트리(Segment Tree)
구간 쿼리와 수정이 빈번하게 일어나는 상황에서 유용하게 사용할 수 있는 자료구조입니다.
배열의 특정 구간에 대한 정보를 빠르게 구하거나 업데이트할 때 사용되며
구간의 최소값, 최대값, 합 등을 구할 수 있습니다.
세그먼트 트리의 구조
- 세그먼트 트리는 이진 트리 형태로, 각 노드가 배열의 특정 구간을 대표합니다.
- 트리의 루트는 배열의 전체 구간을 대표하고, 각 리프 노드는 배열의 하나의 원소를 대표합니다.
- 내부 노드는 자식 노드의 구간을 합쳐서 더 큰 구간을 대표합니다.
세그먼트 트리의 장점
- 특정 구간에 대한 다양한 연산 결과를 빠르게 구할 수 있습니다.
- 중간 데이터가 변경되어도 전체 구조를 재구축하지 않고 빠르게 반영할 수 있습니다.
세그먼트 트리는 주로 구간 합, 구간 최소, 구간 최대 쿼리 등을 처리하는 데 적합하며, 복잡한 범위 쿼리를 필요로 하는 많은 알고리즘 문제에서 활용됩니다.
-구간합 예시
2024 구간 합 구하기 (세그먼트 트리) [Gold I]
2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고
flrjtwjrjt.tistory.com
-최소값 예시
10868 최솟값 (세그먼트 트리)[Gold I]
10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개
flrjtwjrjt.tistory.com
-구간곱 예시
11505 구간 곱 구하기 (세그먼트 트리) [Gold I]
11505번: 구간 곱 구하기첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고
flrjtwjrjt.tistory.com
'프로그래밍 > 자료구조와 알고리즘' 카테고리의 다른 글
| 동적 계획법 (0) | 2024.05.02 |
|---|---|
| 이항계수 구하기 (0) | 2024.04.27 |
| 트리 순회 (0) | 2024.04.21 |
| 트라이 (Trie) (0) | 2024.04.20 |
| 유클리드 호제법 (0) | 2024.03.28 |