개요
세그먼트 트리는 효율적인 데이터 관리와 빠른 쿼리를 가능하게 해주는 데이터 구조이다.
특히, 누적 합 계산이나 특정 구간의 최대값, 최소값을 빠르게 처리해야 하는 경우 유용하게 쓰인다. 💡
이 글에서는 세그먼트 트리가 해결하는 문제와 그 이유, 작동 원리와 활용 사례에 대해서 살펴본다.
문제 상황 🧐
다음과 같은 배열 {1, 3, 5, 7, 9}를 생각해보자. 이에 대해서 다음과 같은 연산을 해야 하는 상황이다.
- 구간 합 구하기
예를 들어, 배열의 2번째부터 4번째 숫자의 합을 계산하려면3 + 5 + 7 = 15이다. - 값 업데이트
배열의 특정 값을 바꿔야 한다면 어떻게 될까요? 예를 들어, 5를 6으로 변경한다면 배열은{1, 3, 6, 7, 9}로 변한다.
이 배열에 대해, 직관적으로 구간 합을 구하거나 값을 업데이트하려면, 매번 해당 연산을 직접 순회하며 처리해야 할 것이다.
즉, 구간 합의 부분이나 업데이트 위치에 따라 배열의 상당 부분을 훑어봐야 하는 상황이 발생한다.
예를 들어,다음과 같은 배열에서
인덱스: 1 2 3 4 5
값: [1, 3, 5, 7, 9]
여기서 "2번째부터 4번째 숫자의 합"을 구하려고 한다면, 단순 접근 방식은 다음과 같이 작동한다.
- 인덱스 2의 값
3을 읽는다. - 인덱스 3의 값
5를 읽는다. - 인덱스 4의 값
7을 읽는다. - 읽은 값들을 모두 더해
3 + 5 + 7 = 15를 얻는다.
이 경우, 구간 길이가 3이므로 3개의 원소를 방문해야 한다. 만약 구간 길이가 커져서 100개, 1000개의 원소를 합해야 한다면 그만큼 많은 수를 직접 읽고 더해야 한다.
또한 업데이트 시에도 마찬가지로, 다음 배열에서 5를 6으로 변경하려 한다고 할 때,
원래 배열: [1, 3, 5, 7, 9]
변경 후: [1, 3, 6, 7, 9]
값을 업데이트하는 것은 한 위치에 대한 변경이므로 그 자체로는 O(1)처럼 보인다.
하지만 문제는 이후 구간 합을 다시 계산할 때 발생한다. 기존의 합을 기억하지 않고 매번 처음부터 합산한다면, 바뀐 값을 반영하기 위해 다시 많은 원소를 순회해야 한다.
즉, 배열 길이가 n일 때, 한 번의 구간 합 계산 혹은 특정 요소 수정에는 O(n)의 시간 복잡도가 걸리게 된다.⌛
세그먼트 트리를 사용하면?
세그먼트 트리가 이를 개선할 수 있을까?
세그먼트 트리는 구간 합 쿼리와 값 업데이트에서의 비효율성을 해결하기 위해 설계된 데이터 구조로, 작업 시간을 획기적으로 단축한다.
즉, O(n) 대신 O(log n)의 시간 복잡도로 문제를 해결할 수 있다.
세그먼트 트리의 정의와 구조 🌲
세그먼트 트리는 주어진 배열을 기반으로 한 트리 형태의 데이터 구조다.
이 트리의 각 노드는 특정 구간(부분 배열)을 대표하며, 구간의 정보를 저장한다.
- 리프 노드(leaf node): 배열의 각 원소를 나타냄
- 내부 노드(internal node): 해당 노드가 대표하는 구간의 합(또는 다른 연산 결과)을 저장
예를 들어 배열 [1, 3, 5, 7, 9]가 있을 때, 전체 구간을 왼쪽 절반 [1,3]과 오른쪽 절반 [5,7,9]로 나누고, 각각에 대해 다시 왼쪽/오른쪽으로 나누어가며 트리를 구성한다.
[25] <- 전체 구간의 합 (1~5)
/ \
[9] [16] <- 구간 [1~3], [4~5]의 합
/ \ / \
[4] [5] [7] [9] <- 구간 [1~2], [3], [4], [5]의 합
/ \
[1] [3] - 루트 노드는 배열 전체 구간
[1 ~ 5]의 합인1+3+5+7+9=25를 저장한다. - 그 하위 왼쪽 자식 노드는
[1 ~ 3]구간의 합, 즉1 + 3 + 5 = 9를 저장한다. - 오른쪽 자식 노드는
[4 ~ 5]구간의 합, 즉7 + 9 = 16을 저장한다. - 이런 식으로 끝까지 분할해 나간다. 리프 노드에는 실제 배열 요소 하나하나의 값이 들어있게 된다.
1차원으로 시각화된 배열을 통해 살펴보면 다음과 같다.
배열의 실제 인덱스는 0부터 시작하지만 계산의 수월함을 위해 세그먼트 트리는 보통 인덱스 1로 구성한다.
인덱스: 0 1 2 3 4 5 6 7 8 9
값: - 25 9 16 4 5 7 9 1 3
즉 다음과 같다.
트리 형태: [25](1)
/ \
[9](2) [16](3)
/ \ / \
[4](4) [5](5) [7](6)[9](7)
/ \
[1](8) [3](9)
배열 형태:
인덱스: 1 2 3 4 5 6 7 8 9
값: 25 9 16 4 5 7 9 1 3
세그먼트 트리의 작동 방식
1. 구간 합 계산
예를 들어, 배열 {1, 3, 5, 7, 9}에서 "2번째부터 4번째 숫자의 합"을 구한다고 가정해보자.
세그먼트 트리에서는 이 작업이 다음과 같이 이루어진다.
- 쿼리할 구간을 트리 구조에서 탐색한다.
2~4구간이 포함된 노드를 따라가며 필요한 노드의 합을 더한다.
- 각 탐색 단계에서 트리의 깊이만큼 연산하므로 시간 복잡도는 O(log n)이다.
👉 탐색 경로:[4] + [5] + [7] = 15
실제 작동 메커니즘을 구체적으로 살펴보자.
세그먼트 트리 구조는 아래와 같은 상태이다. 각 노드는 특정 구간의 합을 저장하고 있다.
[25] <- 전체 구간의 합 (1~5)
/ \
[9] [16] <- 구간 [1~3], [4~5]의 합
/ \ / \
[4] [5] [7] [9] <- 구간 [1~2], [3], [4], [5]의 합
/ \
[1] [3]
2~4 구간을 어떻게 계산하는지 단계별로 생각해 보면,
(1) 루트 노드 [25]에서 시작
- 루트 노드는 전체 구간
[1~5]의 합을 저장하고 있다. - 우리가 찾는 구간
2~4는 루트 노드에 포함되기 때문에, 루트 노드에서 왼쪽 자식과 오른쪽 자식을 따라 내려간다.
(2) 왼쪽 자식 노드 [9]로 이동
- 왼쪽 자식 노드 [9]는
[1~3]구간의 합을 저장하고 있다. - 구간
2~4와 겹치는 부분이 있기 때문에, 다시 이 노드를 세분화해야 한다.[1~2]와[3]으로 나뉜다.
[1~2]구간 중2는 우리가 원하는 구간에 속하므로, 여기서[3]만 따로 더한다.
(3) 오른쪽 자식 노드 [16]로 이동
- 오른쪽 자식 노드 [16]은
[4~5]구간의 합을 저장한다. - 구간
2~4와 겹치는 부분은[4]이다. 이 값을 포함해 더한다.
이제 구간 2~4에 해당하는 값을 더한다.
2~3에서 구한 값:[3] + [5] = 84~5에서 구한 값:[7]
따라서,
\[
3 + 5 + 7 = 15
\]
트리의 각 단계에서 탐색한 노드를 살펴보면,
탐색 경로:
[25]
/ \
[9] [16]
/ \ / \
[4] -->[5] -->[7] [9]
/ \
[1] -->[3]
더한 노드:
[3] + [5] + [7] = 15
시간 복잡도는 왜 O(log n)일까?
세그먼트 트리는 항상 트리의 깊이만큼(즉, 로그 n 수준)만 탐색한다. 위와 같이 필요한 구간에 해당하는 노드만 빠르게 찾아가서 값을 합친다.
따라서 시간 복잡도가 O(log n) 이다.
예를 들어, 배열의 크기가 1,000,000개라면 단 20번의 탐색으로 구간 합을 구할 수 있다.
트리 형태로 나누어져 있기 때문에 불필요한 구간은 건너뛰고, 필요한 구간만 빠르게 접근할 수 있게 되는 것이 장점이다.
간단한 정리!
- 루트에서 시작
항상 루트 노드에서 시작해서, 필요한 구간이 포함된 자식 노드만 따라 내려가면 된다. - 구간이 겹치는지 확인
계산할 구간과 노드의 구간이 겹치는 경우에만 값을 더한다. - 작게 나누어 합산
필요한 노드의 값을 모아 최종 합을 구하면 끝!
2. 값 업데이트
만약 배열의 3번째 값을 5에서 6으로 변경한다고 가정해보자.
세그먼트 트리에서는 다음과 같은 방식으로 처리한다.
1) 리프 노드에서 해당 값을 찾아 업데이트한다.
5 → 6으로 변경.
2) 값이 변경된 리프 노드로부터 상위 노드까지 영향을 받는 모든 합을 재계산한다.
[4] → [6]으로 업데이트.- 루트 노드도 업데이트되어
[25] → [26]으로 갱신된다.
이 작업 역시 트리의 깊이만큼 연산하므로 O(log n) 시간이 걸린다.
스텝별로 살펴보자.
(1) 리프 노드에서 해당 값을 찾아 변경
- 3번째 원소(값
5)에 해당하는 리프 노드는[5]이다. - 이 노드를
5 → 6으로 변경한다.
[25]
/ \
[9] [16]
/ \ / \
[4] [5] [7] [9]
/ \
[1] [3]
└──> 3번째 값을 5 → 6으로 변경
(2) 상위 노드들의 합을 재계산
- 리프 노드가 바뀌었으니, 이 리프 노드를 포함하는 상위 구간들의 합도 달라진다.
- 리프 노드
[5]가[6]이 되었으므로, 이를 포함한 부모 노드[9](구간 [1~3] 합) 또한9 → 10이 된다.- (왜냐하면
[4] + [6] = 10이기 때문)
- (왜냐하면
- 최종적으로 루트 노드
[25]도25 → 26이 된다.- (왼쪽 자식 [13] 합 10 + 오른쪽 자식 [45] 합
16=26)
- (왼쪽 자식 [13] 합 10 + 오른쪽 자식 [45] 합
다음과 같다.
[25] -> [26]
/ \
[9] -> [10] [16]
/ \ / \
[4] [5] -> [6] [7] [9]
/ \
[1] [3]
화살표로 표시된 부분이 업데이트되어 바뀐 노드들이다.
정리해보면 배열이 {1, 3, 5, 7, 9}에서 {1, 3, 6, 7, 9}로 업데이트된 상황에서,
- 리프 노드 [5] → [6] 갱신
- 상위 노드 [9] → [10] 갱신
- 루트 노드 [25] → [26] 갱신
되었다.
구간 합에서와 마찬가지로, 배열 원소가 n개라면 트리의 높이는 대략 O(log n) 이므로, 업데이트 작업은 O(log n) 시간에 처리된다.
예를 들어, 배열 크기가 1,000,000이라도 약 20번 정도의 업데이트만으로 전체 구간 합이 즉시 반영된다.
간단 정리
1) 바꿀 값을 찾는다
- 리프 노드 중에서 변경하고자 하는 배열 원소에 해당하는 노드를 찾는다.
2) 값을 변경한다
- 해당 리프 노드의 값을 새 값으로 갱신한다.
3)부모 노드를 거슬러 올라가며 합을 업데이트
- 변경된 리프 노드부터 루트 노드까지 올라가면서, 각 노드가 저장하고 있는 구간 합을 다시 계산하고 갱신한다.
4) 작은 연산 횟수로 빠른 업데이트
- 트리의 깊이(log n)에 비례하는 연산만 필요하므로, 대용량 배열에서도 빠르게 작동한다.
세그먼트 트리 구현
이제 세그먼트 트리를 구현해보자.
Java 코드를 기반으로 Build, Update, Query라는 세 가지 핵심 기능을 단계별로 살펴본다.
0. 생성자
먼저 생성자를 작성할 때 사용할 필드를 다음과 같이 초기화한다.
public SegmentTreeTest(int[] array) {
this.n = array.length;
int height = (int) Math.ceil(Math.log(n) / Math.log(2));
int maxSize = 2 * (int) Math.pow(2, height) - 1;
tree = new int[maxSize];
buildTree(array, 0, 0, n - 1);
}1) n = array.length
- 입력 배열의 크기를 저장하여, 쿼리와 업데이트에서 유효 범위 검사를 수행하기 위해 필요하다.
2) 트리 배열 크기 계산 (maxSize)
int height = (int) Math.ceil(Math.log(n) / Math.log(2));
int maxSize = 2 * (int) Math.pow(2, height) - 1;
- 세그먼트 트리는 완전 이진 트리로, 노드의 총 개수는 2^(h+1) - 1이 필요하다.
3) tree = new int[maxSize]
- 세그먼트 트리의 노드를 저장할 배열을 초기화한다. 0으로 기본값을 설정한 후, 빌드 과정에서 채워 넣는다.
4) buildTree(array, 0, 0, n - 1)
- 입력 배열 값을 기반으로 트리를 생성한다. 재귀적으로 구간 값을 계산하여 각 노드에 저장한다.
배열 {1, 3, 5, 7, 9} 를 예시로 한다면, 다음과 같다.
1. Build: 세그먼트 트리 생성
이제 Build는 주어진 배열을 기반으로 세그먼트 트리를 생성해보자.
트리의 각 노드는 배열의 특정 구간에 해당하는 값을 저장한다(예: 구간 합, 최소값 등).
private void buildTree(int[] array, int treeIndex, int left, int right) {
if (left == right) {
// 리프 노드: 배열의 값을 트리에 복사
tree[treeIndex] = array[left];
return;
}
// 구간을 반으로 나누어 재귀적으로 트리 생성
int mid = left + (right - left) / 2;
buildTree(array, 2 * treeIndex + 1, left, mid); // 왼쪽 자식
buildTree(array, 2 * treeIndex + 2, mid + 1, right); // 오른쪽 자식
// 현재 노드 값은 두 자식 노드 값의 합/최소값/최대값 등
tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2];
}
실행 과정
- 주어진 배열을 리프 노드로 사용하여 트리를 만든다.
- 부모 노드는 자식 노드들의 값을 기반으로 생성된다.
- 재귀적으로 트리를 구성하며, 트리의 높이는
O(log n)이 된다.
예를 들어, build 트리의 재귀를 스텝별로 들어가보면 가장 먼저 왼쪽 끝의 leaf 노드가 1로 초기화 된다.
- 루트 노드 생성 (tree[0])
- 호출: buildTree(array, 0, 0, 4)
- 구간: [0, 4] → 중간점 mid = 2
- 왼쪽 자식: buildTree(array, 1, 0, 2)
→ 왼쪽이 계속 호출됨 + 인덱스는 *2 + 1로 누적
- 왼쪽 서브트리 생성 (tree[1])
- 호출: buildTree(array, 1, 0, 2)
- 구간: [0, 2] → 중간점 mid = 1
- 왼쪽 자식: buildTree(array, 3, 0, 1)
→ 왼쪽이 계속 호출됨 + 인덱스는 *2 + 1로 누적
- 왼쪽-왼쪽 서브트리 생성 (tree[3])
- 호출: buildTree(array, 3, 0, 1)
- 구간: [0, 1] → 중간점 mid = 0
- 왼쪽 자식: buildTree(array, 7, 0, 0)
→ 왼쪽이 계속 호출됨 + 인덱스는 *2 + 1로 누적
- 리프 노드 생성 (tree[7])
- 호출: buildTree(array, 7, 0, 0)
- 구간: [0, 0]
- 동작: tree[7] = array[0] = 1
- 리프 노드 값 1이 인덱스 7에 저장
즉, 트리의 가장 왼쪽 리프 노드가 재귀적으로 내려가면서 배치된다.
그 다음 재귀에서는 데이터 초기화 후 return이 되면서 오른쪽이 초기화된다.
if (left == right) {
tree[treeIndex] = array[left];
return;
}
이때 호출되는 오른쪽 build 파라미터는 다음과 같다.
buildTree(array, 8, 1, 1)
오른쪽 리프 노드 생성 (tree[8])
1) 호출: buildTree(array, 8, 1, 1)
- 부모 노드: tree[3]
- 구간: [1, 1] → 단일 원소로, 더 이상 분할하지 않고 리프 노드로 초기화
2) 동작:
- tree[8] = array[1] = 3
3) 결과:
- 값 3이 트리의 인덱스 8에 저장
즉, 3단계 재귀 스텝에서 트리 배열의 인덱스에 값이 채워지는 과정을 살펴보면,
1. buildTree(array, 3, 0, 1) → tree[3] = 왼쪽 서브 구간 [0, 1]
2. ├── buildTree(array, 7, 0, 0) → tree[7] = array[0] = 1
3. └── buildTree(array, 8, 1, 1) → tree[8] = array[1] = 3
이때 트리는 다음과 같다.
인덱스: 0 1 2 3 4 5 6 7 8
노드 값: [ ] [ ] [ ] [ ] [ ] [ ] [ ] [1] [3]
그 다음 재귀는 어떻게 될까? 오른쪽 build까지 전부 호출되었으므로 마지막 코드가 실행된다.
tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2];
즉, 구간 [0, 1]의 값을 계산이 되는 것이며,
- left = 0, right = 1
- 두 자식 노드의 값을 재귀 호출로 초기화:
- buildTree(array, 7, 0, 0) → tree[7] = 1
- buildTree(array, 8, 1, 1) → tree[8] = 3
- 결과: tree[3] = 4
1. buildTree(array, 3, 0, 1) → tree[3] = 구간 [0, 1]의 합
2. ├── buildTree(array, 7, 0, 0) → tree[7] = array[0] = 1
3. └── buildTree(array, 8, 1, 1) → tree[8] = array[1] = 3
4. tree[3] = tree[7] + tree[8] → tree[3] = 1 + 3 = 4
이와 같은 흐름에 따라 전체 트리 빌드 과정을 정리해보면 다음과 같다.
1. buildTree(array, 0, 0, 4) → tree[0] = 전체 구간 합
2. ├── buildTree(array, 1, 0, 2) → tree[1] = 왼쪽 구간 합 [0, 2]
3. │ ├── buildTree(array, 3, 0, 1) → tree[3] = 왼쪽 [0, 1]
4. │ │ ├── buildTree(array, 7, 0, 0) → tree[7] = array[0] = 1
5. │ │ └── buildTree(array, 8, 1, 1) → tree[8] = array[1] = 3
6. │ └── buildTree(array, 4, 2, 2) → tree[4] = array[2] = 5
7. └── buildTree(array, 2, 3, 4) → tree[2] = 오른쪽 구간 합 [3, 4]
8. ├── buildTree(array, 5, 3, 3) → tree[5] = array[3] = 7
9. └── buildTree(array, 6, 4, 4) → tree[6] = array[4] = 9
전체 트리 배열 시각화
인덱스: 0 1 2 3 4 5 6 7 8 9 10
노드 값: [25] [9] [16] [4] [5] [7] [9] [1] [3] [5] ...
배열 {1, 3, 5, 7, 9}로 생성한 세그먼트 트리는 최종적으로 다음과 같다.
[25]
/ \
[9] [16]
/ \ / \
[4] [5] [7] [9]
/ \
[1] [3]
2. Update: 값 변경
Update는 배열의 특정 값이 변경되었을 때, 세그먼트 트리의 해당 구간 값을 갱신한다.
코드 및 설명
void updateValueUtil(int ss, int se, int i, int diff, int si) {
if (i < ss || i > se) {
// 변경된 인덱스가 현재 구간 범위 밖이면 종료
return;
}
// 현재 노드 값 업데이트
tree[si] = tree[si] + diff;
if (se != ss) {
// 리프 노드가 아니면 자식 노드 갱신
int mid = getMid(ss, se);
updateValueUtil(ss, mid, i, diff, 2 * si + 1);
updateValueUtil(mid + 1, se, i, diff, 2 * si + 2);
}
}실행 과정
- 배열 값이
i에서new_val로 변경된다. diff = new_val - arr[i]를 계산하여, 해당 노드와 상위 노드의 값을 갱신한다.- 루트까지 영향을 받는 모든 노드를 갱신한다.
- 배열
{1, 3, 5, 7, 9}에서arr[2] = 6으로 변경:diff = 6 - 5 = 1- 영향을 받은 노드들:
[26]
/ \
[10] [16]
/ \ / \
[4] [6] [7] [9]
/ \
[1] [3]
3. Query: 구간 값 계산
Query는 특정 구간(예: qs~qe)에 대한 값을 계산한다(구간 합, 최소값 등).
private int query(int treeIndex, int left, int right, int queryLeft, int queryRight) {
if (queryLeft <= left && right <= queryRight) {
// 현재 구간이 쿼리 범위에 완전히 포함됨
return tree[treeIndex];
}
if (right < queryLeft || left > queryRight) {
// 현재 구간이 쿼리 범위 밖임
return 0; // 합 기준, 다른 연산에는 적절한 초기값 사용
}
// 구간이 쿼리 범위와 겹침
int mid = left + (right - left) / 2;
return query(2 * treeIndex + 1, left, mid, queryLeft, queryRight) +
query(2 * treeIndex + 2, mid + 1, right, queryLeft, queryRight);
}실행 과정
- 쿼리 범위가 노드 범위에 포함되면 값을 반환한다.
- 쿼리 범위가 노드 범위 밖이면 0(또는 초기값)을 반환한다.
- 쿼리 범위가 겹치면 자식 노드로 탐색을 이어간다.
- 배열
{1, 3, 5, 7, 9}에서2~4구간 합:
[25]
/ \
[9] [16]
\ /
[5] [7]- 결과:
3 + 5 + 7 = 15
이제 결합 및 실행해보자.
public class Main {
public static void main(String[] args) {
int[] array = {1, 3, 5, 7, 9};
SegmentTree st = new SegmentTree(array);
// 구간 쿼리
System.out.println("구간 합 (2~4): " + st.query(1, 3));
// 값 업데이트
st.updateValue(array, array.length, 2, 6);
System.out.println("업데이트 후 구간 합 (2~4): " + st.query(1, 3));
}
}
전체 코드
public class SegmentTreeTest {
private int[] tree; // 세그먼트 트리 배열
private int n; // 입력 배열의 크기
// 세그먼트 트리 생성자
public SegmentTreeTest(int[] array) {
this.n = array.length;
int height = (int) Math.ceil(Math.log(n) / Math.log(2));
int maxSize = 2 * (int) Math.pow(2, height) - 1;
tree = new int[maxSize];
buildTree(array, 0, 0, n - 1);
}
// 세그먼트 트리 생성
private void buildTree(int[] array, int treeIndex, int left, int right) {
if (left == right) {
tree[treeIndex] = array[left];
return;
}
int mid = left + (right - left) / 2;
buildTree(array, 2 * treeIndex + 1, left, mid);
buildTree(array, 2 * treeIndex + 2, mid + 1, right);
tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2];
}
// 값 업데이트
public void updateValue(int[] array, int n, int index, int newValue) {
if (index < 0 || index >= n) {
System.out.println("잘못된 인덱스");
return;
}
int diff = newValue - array[index];
array[index] = newValue;
updateValueUtil(0, 0, n - 1, index, diff);
}
private void updateValueUtil(int treeIndex, int left, int right, int index, int diff) {
if (index < left || index > right) return;
tree[treeIndex] += diff;
if (left != right) {
int mid = left + (right - left) / 2;
updateValueUtil(2 * treeIndex + 1, left, mid, index, diff);
updateValueUtil(2 * treeIndex + 2, mid + 1, right, index, diff);
}
}
// 구간 합 쿼리
public int query(int queryLeft, int queryRight) {
return queryUtil(0, 0, n - 1, queryLeft, queryRight);
}
private int queryUtil(int treeIndex, int left, int right, int queryLeft, int queryRight) {
if (queryLeft <= left && right <= queryRight) {
return tree[treeIndex];
}
if (right < queryLeft || left > queryRight) {
return 0; // 합 기준 초기값
}
int mid = left + (right - left) / 2;
return queryUtil(2 * treeIndex + 1, left, mid, queryLeft, queryRight) +
queryUtil(2 * treeIndex + 2, mid + 1, right, queryLeft, queryRight);
}
// 테스트 실행
public static void main(String[] args) {
int[] array = {1, 3, 5, 7, 9};
SegmentTreeTest st = new SegmentTreeTest(array);
// 구간 합 쿼리
System.out.println("구간 합 (2~4): " + st.query(1, 3));
// 값 업데이트
st.updateValue(array, array.length, 2, 6);
System.out.println("업데이트 후 구간 합 (2~4): " + st.query(1, 3));
}
}
Q&A
🤔 1. 세그먼트 트리의 경우 생성을 하는 부분에서도 logn 인가?
세그먼트 트리(Segment Tree)는 데이터 구조에서 효율적인 쿼리 및 업데이트를 수행하기 위해 사용된다. 트리의 생성(초기화) 시간 복잡도는 데이터를 처음에 트리에 넣고 구조를 만드는 과정에서 영향을 받는다.
세그먼트 트리 생성의 시간 복잡도
세그먼트 트리는 입력 데이터 크기를 n이라 할 때, 대략 2n2n개의 노드가 필요하다(리프 노드 + 내부 노드). 트리 구조를 생성하려면 다음과 같은 과정을 거친다.
- 리프 노드 초기화: 입력 배열의 각 원소를 리프 노드에 저장한다.
- 내부 노드 초기화: 리프 노드부터 부모 노드로 올라가며 각 내부 노드를 계산한다(예: 구간 합, 최소값 등).
따라서, 리프 노드 초기화는 O(n), 내부 노드 계산은 O(n) 시간이 걸리므로, 전체 트리 생성 과정은 O(n) 시간 복잡도를 가진다.
🤔 2. 그렇다면 실제 시간을 고려하면 인덱스를 전체 탐색하는 것보다 나을바가 없는 거 같은데 왜 사용하는 건가?
배열을 사용해서 구간 합이나 최소값을 계산하는 경우, 각 쿼리마다 배열의 일부를 탐색해야 하므로 쿼리 당 시간 복잡도는 O(n)이다. 업데이트를 할 때도 기존 값을 변경하고 다시 계산해야 하므로, 비슷한 O(n) 시간이 걸릴 수 있다.
다만 세그먼트 트리는 한 번 초기화한 뒤에 여러 번 구간 쿼리와 업데이트 작업을 빠르게 처리할 수 있다.
각각의 작업이 O(logn)이므로, 다음과 같은 경우에 매우 유리하다.
1) 구간 쿼리가 많을 때:
- 예를 들어, 데이터의 구간 합/최소값/최대값 등을 자주 요청하는 경우, 배열 전체 탐색으로 O(n)씩 반복 수행하는 것보다 세그먼트 트리로 O(logn)에 처리하는 것이 훨씬 효율적이다.
2) 데이터가 자주 변경될 때 (업데이트):
- 업데이트마다 전체 배열을 다시 계산하는 O(n) 작업 대신, 세그먼트 트리의 특정 경로만 갱신하여 O(logn)에 처리할 수 있다.
3) 대규모 데이터 처리:
- 데이터 크기 n이 커질수록, 세그먼트 트리의 효율성이 두드러진다. 예를 들어, n=1,000,000 이라면 배열 탐색은 O(n)=1,000,000, 세그먼트 트리는 O(logn)≈20O 수준으로 작업 시간이 크게 차이 난다.
실제 예시: 세그먼트 트리 vs 배열
배열 탐색:
- 구간 합 쿼리 100번 → O(100n)
- 업데이트 50번 → O(50n)
- 총 시간 복잡도: O(150n)
세그먼트 트리:
- 초기화 → O(n)
- 구간 합 쿼리 100번 → O(100logn)
- 업데이트 50번 → O(50logn)
- 총 시간 복잡도: O(n+150logn)
큰 n일수록 배열 탐색은 비효율적이고, 세그먼트 트리는 상대적으로 빠르게 처리할 수 있다.
결론
세그먼트 트리는 초기화 비용이 크지만, 구간 작업이 많거나 데이터 업데이트가 빈번한 상황에서 배열 탐색보다 훨씬 효율적이다. 이런 이유로, 실시간 데이터 처리나 쿼리가 반복되는 문제에서 세그먼트 트리를 사용할 수 있다.
🤔 3. 실제 데이터베이스나 현업에서 세그먼트 트리가 사용되는 사례가 어떻게 될까?
(1) 시간 구간별 데이터 분석
- 예시: 로그 데이터, 트래픽 데이터, 주식 거래 데이터
- 특정 시간 구간에 대한 합계, 최대값, 최소값, 또는 다른 통계를 계산하는 데 유용
- 사용 이유:
- 대규모 데이터에서 특정 시간 구간의 값을 반복적으로 분석할 때 세그먼트 트리가 효율적
- 예를 들어, 지난 1시간 동안의 평균 트래픽을 반복적으로 계산하거나, 특정 주식의 최저가를 특정 구간에서 빠르게 추출.
(2) 실시간 데이터 분석
- 예시: IoT 데이터, 스트리밍 서비스
- IoT 센서의 실시간 데이터를 수집하면서 특정 시간 구간에 대해 평균값, 합계 등을 지속적으로 계산.
- 세그먼트 트리의 업데이트와 쿼리 효율성을 이용해 빠르게 통계를 유지할 수 있음.
(3) 게임 서버
- 예시: 게임 랭킹 시스템
- 여러 플레이어의 점수 데이터를 관리하며, 특정 범위의 랭킹을 쿼리하거나, 점수가 업데이트될 때 실시간으로 계산.
- 특정 점수 구간에서 몇 명의 유저가 있는지, 특정 순위의 점수를 빠르게 찾는 데 유용.
(4) 광고 기술
- 예시: 광고 클릭 분석
- 광고의 클릭 데이터를 시간 단위로 저장하고, 특정 시간 구간에서의 클릭 수를 빠르게 분석.
- 광고의 성과를 실시간으로 업데이트하거나 쿼리할 때 세그먼트 트리가 유용.
끝.
'알고리즘' 카테고리의 다른 글
| 요세푸스 문제의 마지막 남은 사람을 수학적 귀납법으로 도출한 점화식으로 찾아보자 (0) | 2024.10.13 |
|---|---|
| 모노토닉 스택(monotonic stack) 개념, 작동원리 + 예제 문제들 (주식 가격, 탑, 히스토그램에서 가장 큰 직사각형 찾기) (0) | 2024.10.06 |
