1. 개요
Segment Tree배열의 연속한 구간에 대해 질의(query)와 갱신(update)를 효율적으로 수행할 수 있도록 설계된 이진 트리 기반 자료구조.
구간 합, 구간 최대·최소, 구간 곱, 구간 XOR과 같은 구간 연산들을 [math(O(\log N))] 시간만에 처리할 수 있다.
2. 설명
아래와 같은 문제를 생각해보자.- 길이가 [math(N)]인 배열 [math(A)]가 주어진다.
- 그 다음, 아래 명령들이 합쳐서 [math(M)]개 주어진다.
- 갱신: [math(A_i)]의 값을 [math(x)]로 갱신한다.
- 질의: [math(i)]부터 [math(j)]까지의 원소들에 대한 연산의 값([math(A_i \oplus \dots \oplus A_j)])을 구한다.
단순히 배열 [math(A)]를 관리하여 풀면 각 갱신은 [math(O(1))]만에 처리할 수 있지만 질의는 [math(O(j - i))]번의 연산을 수행해야하므로 [math(O(N))]이 걸린다. 질의를 빠르게 수행하기 위해 누적합 배열 [math(B\,(B_k = A_0 \oplus \dots \oplus A_{k-1}))]를 관리하는 방법을 생각할 수 있다. 이 경우, [math(A_i \oplus \dots \oplus A_j = B_j \ominus B_{i-1})]로 계산할 수 있는 [math(\ominus)]가 존재하면 질의는 [math(O(1))]만에 처리할 수 있으나, 갱신 명령이 들어오면 [math(B_i)]부터 [math(B_{N+1})]까지의 값을 갱신해야하기 때문에 [math(O(N))]의 시간이 필요하다. 따라서 두 방법 모두 최악 시간 복잡도는 [math(O(NM))]이다.
세그먼트 트리의 아이디어는 배열을 단계화된 구간들로 나눈 완전 이진 트리 구조로 만들어, 질의와 갱신을 모두 [math(O(\log N))]만에 수행하는 것이다.
예를 들어, [math(A = [2, 7, -3, -4, 0, 5, 3, -1])], [math(a \oplus b = a + b)]일 때, 세그먼트 트리는 아래와 같이 구성된다. 리프 노드에 [math(A_i)]를 저장하고, 각 부모 노드는 자식 노드의 값을 연산하여 저장하는 것이다.
| <colbgcolor=#f5f5f5,#2d2f34>트리 | 9 | |||||||
| 2 | 7 | |||||||
| 9 | -7 | 5 | 2 | |||||
| 2 | 7 | -3 | -4 | 0 | 5 | 3 | -1 | |
| [math(A_i)] | 2 | 7 | -3 | -4 | 0 | 5 | 3 | -1 |
| [math(i)] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
여기에 갱신 연산 [math(A_4 := -2)]을 수행해보자.
| <colbgcolor=#f5f5f5,#2d2f34>트리 | 7 | |||||||
| 2 | 5 | |||||||
| 9 | -7 | 3 | 2 | |||||
| 2 | 7 | -3 | -4 | -2 | 5 | 3 | -1 | |
| [math(A_i)] | 2 | 7 | -3 | -4 | -2 | 5 | 3 | -1 |
| [math(i)] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
이제 질의 연산 [math(A_1 \oplus \dots \oplus A_5)]을 수행해보자. 세그먼트 트리의 구조를 이용하여 [math(A_1 \oplus \dots \oplus A_5 = (A_1) \oplus (A_2 \oplus A_3) \oplus (A_4 \oplus A_5))]로 나누어 계산할 수 있다.
| <colbgcolor=#f5f5f5,#2d2f34>트리 | 7 | |||||||
| 2 | 5 | |||||||
| 9 | -7 | 3 | 2 | |||||
| 2 | 7 | -3 | -4 | -2 | 5 | 3 | -1 | |
| [math(A_i)] | 2 | 7 | -3 | -4 | -2 | 5 | 3 | -1 |
| [math(i)] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
2.1. 시간·공간 복잡도
| <colbgcolor=#f5f5f5,#2d2f34> 자료구조 | 시간복잡도 | 공간복잡도 | ||
| 전처리 | 질의 | 갱신 | ||
| 단순 배열 | [math(O(N))] | [math(O(N))] | [math(O(1))] | [math(O(N))] |
| 누적 합 배열 | [math(O(N))] | [math(O(1))] | [math(O(N))] | [math(O(N))] |
| 세그먼트 트리 | [math(O(N))] | [math(O(\log N))] | [math(O(\log N))] | [math(O(N))] |