세그먼트 트리
- 여러 개의 데이터가 존재할 때 특정 구간의 합(최솟값, 곱 등)을 구하는데 사용하는 자료구조이다.
- 트리 종류 중 하나로 이진 트리의 형태이며, 특정 구간의 합을 가장 빠르게 구할 수 있다.
- 시간 복잡도는 O(logN)
언제 사용할까 ?
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
- 위와 같은 배열에서 2부터 8까지의 데이터를 더하려면 범위의 원소를 하나씩 다 더하면 된다.
- 이러한 방식으로 다른 특정 구간의 합을 구한다고 고려했을 때 앞에서 하나씩 더하므로 데이터의 갯수가 N이면 시간 복잡도는 O(N)이다.
- 따라서, 이러한 방식으로 구간의 합을 구하면 속도가 너무 느리기 때문에 더 좋은 방법이 필요하다.
- 이 때, 더 좋은 방법은 세그먼트 트리(Segment Tree)를 사용하는 것이다.
세그먼트 트리란 ?
- 맨 밑(leaf) 노드는 자기 자신의 값을 가지고 부모 노드는 left + right의 값을 가진다.
- 이 때, 부모 노드의 left + right은 min(left, right) 혹은 max(left, right), 등으로 대체될 수 있다.
- 중요한 것은 구간의 합이 아니라 구간 트리라는 부분이다.
- 세그먼트 트리의 구현은 bottom up / top down 두 가지로 구현이 가능하다.
- bottom up은 접근성과 성능이 좋고,
- top down은 확장성이 좋지만, 일반적으로 재귀를 사용하여 성능이 떨어진다.