Baymax

열심히 화이팅

2 분 소요

1. 세그먼트 트리의 정의와 필요성

1.1 세그먼트 트리란?

  • 정의: 구간 쿼리를 효율적으로 처리하기 위한 트리 자료구조
  • 특징:
    • 구간 합, 최대값, 최소값 등의 연산을 O(logN)에 처리
    • 데이터 업데이트도 O(logN)에 가능
    • 메모리는 원본 배열의 4배 정도 필요

1.2 활용 사례

  • 구간 합 계산
  • 구간 최대/최소값 찾기
  • 구간 곱 계산
  • 히스토그램에서 가장 큰 직사각형 찾기

2. 세그먼트 트리 구조

2.1 기본 구조

세그먼트 트리 구조 세그먼트 트리의 기본 구조

2.2 구조적 특징

1. Complete Binary Tree 형태
2. 리프 노드를 제외한 모든 노드는 두 자식의 값을 합친 결과
3. 높이: O(logN)
4. 필요한 노드 수: 4N

3. 세그먼트 트리 구현

3.1 구간 합 예제

원본 배열: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

3.1.1 단순 계산 방식 (O(N))

// 구간 [6,9]의 합
int sum = 0;
for(int i = 6; i <= 9; i++) sum += arr[i];  // 7+8+9+10 = 34

3.1.2 누적 합 방식 (O(1), 갱신 O(N))

// 누적합 배열
int cumsum[10] = {1, 3, 6, 10, 15, 21, 28, 36, 45, 55};
// 구간 [6,9]의 합
int sum = cumsum[9] - cumsum[5];  // 55 - 21 = 34

3.1.3 세그먼트 트리 방식 (O(logN))

                 [1-10]:55
           /                  \
    [1-5]:15                [6-10]:40
    /        \              /         \
[1-3]:6    [4-5]:9    [6-8]:24    [9-10]:19

3.2 기본 연산 구현

3.2.1 트리 초기화

int init(int* tree, int node, int s, int e) {
    if(s == e) 
        return tree[node] = arr[s];
    
    int m = (s + e) / 2;
    int a = init(tree, node*2, s, m);
    int b = init(tree, node*2 + 1, m+1, e);
    return tree[node] = a + b;
}

3.2.2 구간 합 쿼리

int query(int* tree, int node, int ts, int te, int qs, int qe) {
    // 완전히 포함되는 경우
    if (ts >= qs && qe >= te) return tree[node];
    
    // 겹치지 않는 경우
    if (te < qs || qe < ts) return 0;
    
    // 부분적으로 겹치는 경우
    int m = (ts + te) / 2;
    return query(tree, node*2, ts, m, qs, qe) + 
           query(tree, node*2+1, m+1, te, qs, qe);
}

3.2.3 값 업데이트

int update(int* tree, int node, int s, int e, int idx, int diff) {
    if (idx < s || e < idx) return tree[node];
    
    tree[node] += diff;
    if (s == e) return tree[node];
    
    int m = (s + e) / 2;
    int a = update(tree, node*2, s, m, idx, diff);
    int b = update(tree, node*2+1, m+1, e, idx, diff);
    return tree[node] = a + b;
}

4. 세그먼트 트리 최적화

4.1 시간 복잡도 비교

| 연산 | 일반 배열 | 누적 합 | 세그먼트 트리 | |——|———–|———|—————| | 구간 쿼리 | O(N) | O(1) | O(logN) | | 값 갱신 | O(1) | O(N) | O(logN) | | 공간 복잡도 | O(N) | O(N) | O(N) |

4.2 최적화 팁

  1. 메모리 최적화
    • 완전 이진 트리 특성을 이용해 배열 크기 최적화
    • 비트 연산으로 노드 인덱스 계산 최적화
  2. 재귀 제거
    • 반복문으로 구현하여 함수 호출 오버헤드 제거
    • 특히 업데이트 연산에서 효과적

💡 참고: 세그먼트 트리는 Lazy Propagation을 통해 구간 업데이트도 O(logN)에 수행할 수 있습니다.

댓글남기기

참고