2026-02-03 | 11 min read | 102 | 자료구조 세그먼트 트리 알고리즘

2-10. 자료구조: Segment Tree (세그먼트 트리)

1. 세그먼트 트리 소개: 효율적인 구간 질의의 해법

세그먼트 트리(Segment Tree)는 주어진 배열(array)의 특정 구간(segment)에 대한 질의(query)를 효율적으로 처리하기 위한 강력한 자료구조입니다. 배열 내 원소들의 합, 최소값, 최대값 등과 같이 구간에 대한 정보를 빠르게 얻고, 배열의 원소를 수정하는 업데이트 연산 또한 효율적으로 처리할 수 있도록 설계되었습니다. 특히, 자료의 갱신이 빈번하게 일어나는 상황에서 구간 쿼리를 빠르게 처리해야 할 때, 세그먼트 트리는 훌륭한 선택이 될 수 있습니다. 이는 기존의 배열 기반 접근 방식인 O(N) 시간 복잡도를 O(log N)으로 획기적으로 개선하며, 효율성을 극대화합니다.

1) 배경: 왜 세그먼트 트리가 필요한가?

배열 arr가 주어졌을 때, arr[i]에서 arr[j]까지의 원소들의 합을 구하는 문제를 생각해 봅시다. 가장 기본적인 방법은 단순히 i부터 j까지의 모든 원소를 순회하며 합을 계산하는 것입니다. 하지만 이러한 접근 방식은 질의가 많아질수록 비효율적입니다. 배열의 크기가 N이고, 각 질의에 대해 O(N)의 시간이 소요되므로, 총 Q개의 질의가 있다면 O(Q * N)의 시간 복잡도를 갖게 됩니다. 또한, 배열의 특정 원소를 수정하는 경우에도, 해당 원소가 포함된 모든 구간의 정보를 다시 계산해야 하므로 비효율적입니다. 세그먼트 트리는 이러한 문제를 해결하기 위해 고안되었습니다.

2) 세그먼트 트리의 장점

세그먼트 트리의 주요 장점은 다음과 같습니다.

  • 빠른 구간 질의: 구간 합, 최소/최대값 등 다양한 연산을 O(log N) 시간에 처리할 수 있습니다.
  • 빠른 업데이트: 배열의 원소 변경 시, 세그먼트 트리도 O(log N) 시간에 업데이트됩니다.
  • 유연성: 다양한 연산(합, 곱, 최소/최대, XOR 등)에 적용 가능합니다.

2. 세그먼트 트리의 구조와 원리

세그먼트 트리는 이진 트리(binary tree) 형태로 구성됩니다. 각 노드는 입력 배열의 특정 구간에 대한 정보를 저장합니다.

세그먼트 트리 구조 설명 뒤

1) 구조

  • 리프 노드(Leaf nodes): 입력 배열의 각 원소를 나타냅니다.
  • 내부 노드(Internal nodes): 자식 노드들의 정보를 기반으로, 특정 구간에 대한 정보를 저장합니다. 예를 들어, 구간 합을 저장하는 세그먼트 트리에서, 내부 노드는 해당 구간의 합을 저장합니다.
  • 트리의 구성:
    • 루트 노드는 전체 배열을 나타냅니다.
    • 각 노드는 해당 구간을 두 개의 하위 구간으로 나눕니다.
    • 각 하위 구간은 자식 노드에 의해 표현됩니다.

2) 빌드(Build) 과정

세그먼트 트리를 구성하는 과정은 다음과 같습니다.

  1. 리프 노드 초기화: 입력 배열의 각 원소 값을 리프 노드에 할당합니다.
  2. 내부 노드 정보 계산: 자식 노드의 정보를 이용하여 부모 노드의 정보를 계산합니다. 예를 들어, 구간 합을 구하는 경우, 자식 노드의 합을 더하여 부모 노드의 합을 계산합니다.
  3. 재귀적 구성: 이러한 과정을 루트 노드까지 반복합니다.

3) 구간 질의 (Query)

세그먼트 트리에서 특정 구간에 대한 질의를 처리하는 과정은 다음과 같습니다.

  1. 루트 노드에서 시작: 질의하려는 구간과 현재 노드의 구간을 비교합니다.
  2. 완전 포함: 현재 노드의 구간이 질의 구간에 완전히 포함되면, 해당 노드의 정보를 반환합니다.
  3. 부분 겹침: 현재 노드의 구간이 질의 구간과 겹치면, 자식 노드들을 재귀적으로 탐색합니다.
  4. 완전 불포함: 현재 노드의 구간이 질의 구간과 겹치지 않으면, 해당 노드를 무시합니다.
  5. 결과 조합: 재귀 호출의 결과를 조합하여 최종 결과를 얻습니다.

4) 업데이트 (Update)

세그먼트 트리에서 특정 원소를 업데이트하는 과정은 다음과 같습니다.

  1. 리프 노드 업데이트: 업데이트하려는 원소에 해당하는 리프 노드의 값을 변경합니다.
  2. 부모 노드 업데이트: 변경된 리프 노드의 조상 노드들을 재귀적으로 탐색하며 정보를 업데이트합니다.
  3. 결과 전파: 루트 노드까지 업데이트를 전파합니다.

3. 세그먼트 트리 구현 (C++ 예시)

구간 합을 구하는 세그먼트 트리의 간단한 C++ 구현 예시입니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 세그먼트 트리를 나타내는 클래스
class SegmentTree {
private:
    vector<int> tree; // 세그먼트 트리 배열
    vector<int> arr;  // 입력 배열
    int n;            // 입력 배열의 크기

    // 트리 노드 초기화 함수 (재귀)
    void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start]; // 리프 노드에 값 할당
        } else {
            int mid = (start + end) / 2;
            build(2 * node + 1, start, mid);        // 왼쪽 자식 노드
            build(2 * node + 2, mid + 1, end);    // 오른쪽 자식 노드
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2]; // 자식 노드 값의 합
        }
    }

    // 구간 합을 구하는 함수 (재귀)
    int query(int node, int start, int end, int left, int right) {
        if (right < start || end < left) { // 구간이 겹치지 않음
            return 0; // 해당 없음
        }
        if (left <= start && end <= right) { // 구간이 완전히 포함됨
            return tree[node];
        }
        int mid = (start + end) / 2;
        int leftSum = query(2 * node + 1, start, mid, left, right);   // 왼쪽 자식 노드
        int rightSum = query(2 * node + 2, mid + 1, end, left, right); // 오른쪽 자식 노드
        return leftSum + rightSum; // 두 구간의 합 반환
    }

    // 노드 값 업데이트 함수 (재귀)
    void update(int node, int start, int end, int idx, int val) {
        if (start == end) { // 리프 노드에 도달
            tree[node] = val; // 값 변경
            arr[idx] = val;   // 원본 배열도 변경
        } else {
            int mid = (start + end) / 2;
            if (start <= idx && idx <= mid) {    // 왼쪽 자식 노드
                update(2 * node + 1, start, mid, idx, val);
            } else {                           // 오른쪽 자식 노드
                update(2 * node + 2, mid + 1, end, idx, val);
            }
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2]; // 부모 노드 값 업데이트
        }
    }

public:
    // 생성자: 입력 배열을 받아 세그먼트 트리를 생성
    SegmentTree(const vector<int>& inputArr) : arr(inputArr), n(inputArr.size()) {
        tree.resize(4 * n); // 트리 배열 크기 할당 (최대 4 * n)
        build(0, 0, n - 1);  // 트리 구성
    }

    // 구간 합을 구하는 함수 (public)
    int query(int left, int right) {
        return query(0, 0, n - 1, left, right);
    }

    // 특정 인덱스의 값을 업데이트하는 함수 (public)
    void update(int idx, int val) {
        update(0, 0, n - 1, idx, val);
    }
};

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    SegmentTree st(arr);

    // 구간 [1, 3]의 합
    cout << "Sum of [1, 3]: " << st.query(1, 3) << endl; // 출력: 15 (3 + 5 + 7)

    // 인덱스 2의 값을 10으로 업데이트
    st.update(2, 10);

    // 업데이트 후 구간 [1, 3]의 합
    cout << "Sum of [1, 3] after update: " << st.query(1, 3) << endl; // 출력: 20 (3 + 10 + 7)

    return 0;
}

1) 코드 해설

  • SegmentTree 클래스는 세그먼트 트리를 나타냅니다.
  • tree는 세그먼트 트리 배열을, arr은 입력 배열을 저장합니다.
  • build() 함수는 재귀적으로 트리를 구성합니다.
  • query() 함수는 주어진 구간의 합을 구합니다.
  • update() 함수는 특정 인덱스의 값을 변경하고, 해당 노드들을 업데이트합니다.

2) 시간 복잡도

  • 구축 (build): O(N)
  • 쿼리 (query): O(log N)
  • 업데이트 (update): O(log N)

4. 세그먼트 트리의 응용

세그먼트 트리는 다양한 문제 해결에 활용될 수 있습니다.

1) 구간 합 (Range Sum)

가장 기본적인 활용 사례로, 특정 구간의 합을 빠르게 계산할 수 있습니다. 위에서 제시된 C++ 코드가 구간 합을 구하는 세그먼트 트리의 예시입니다.

2) 구간 최소/최대 (Range Minimum/Maximum)

구간 내의 최소값 또는 최대값을 빠르게 구할 수 있습니다. 세그먼트 트리의 각 노드에 해당 구간의 최소/최대값을 저장하면 됩니다.

3) 구간 곱 (Range Product)

구간 내의 모든 원소의 곱을 계산할 수 있습니다. 단, 곱셈 연산 시 오버플로우에 유의해야 합니다.

4) 기타 응용

  • 동적 배열 관리: 배열의 원소 추가/삭제 연산이 빈번한 경우, 세그먼트 트리를 이용하여 효율적으로 관리할 수 있습니다.
  • 2D 세그먼트 트리: 2차원 배열에 대한 질의를 처리할 수 있습니다.
  • 레이지 프로퍼게이션 (Lazy Propagation): 구간 업데이트를 효율적으로 처리하기 위한 기법입니다.

5. 레이지 프로퍼게이션 (Lazy Propagation)

레이지 프로퍼게이션(Lazy Propagation)은 세그먼트 트리의 성능을 더욱 향상시키는 고급 기술입니다. 특히, 구간 업데이트 연산이 빈번하게 발생하는 경우에 효과적입니다.

1) 문제점: 구간 업데이트의 비효율성

일반적인 세그먼트 트리에서 구간 업데이트는 O(log N)의 시간 복잡도를 갖지만, 각 노드를 일일이 업데이트해야 하므로, 업데이트 연산이 여러 번 반복되면 성능 저하가 발생할 수 있습니다. 예를 들어, [i, j] 구간의 모든 원소를 특정 값으로 변경하는 경우, 해당 구간에 속하는 모든 노드를 업데이트해야 합니다.

2) 레이지 프로퍼게이션의 원리

레이지 프로퍼게이션은 이러한 문제를 해결하기 위해, 업데이트 정보를 부모 노드에 "미루어" 저장하는 방식을 사용합니다.

  • 레이지 배열: 각 노드에 추가적인 lazy 값을 저장하여, 해당 노드에 적용해야 할 업데이트 정보를 저장합니다.
  • 지연된 업데이트: 구간 업데이트 시, 해당 구간을 완전히 포함하는 노드에 lazy 값을 저장하고, 자식 노드에 대한 업데이트는 미룹니다.
  • 정보 전파: 쿼리 또는 다른 업데이트 연산 시, 필요한 경우 lazy 값을 자식 노드에 전파(propagation)하고, 해당 노드를 업데이트합니다.

레이지 프로퍼게이션 개념 설명 뒤

3) 레이지 프로퍼게이션 구현 (C++ 예시)

구간 합을 구하고, 구간에 값을 더하는 연산을 지원하는 세그먼트 트리의 레이지 프로퍼게이션 구현 예시입니다.

#include <iostream>
#include <vector>

using namespace std;

class SegmentTreeLazy {
private:
    vector<int> tree;     // 세그먼트 트리 배열
    vector<int> lazy;     // 레이지 배열
    vector<int> arr;      // 입력 배열
    int n;                // 입력 배열의 크기

    // 트리 노드 초기화 (재귀)
    void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start]; // 리프 노드에 값 할당
        } else {
            int mid = (start + end) / 2;
            build(2 * node + 1, start, mid);        // 왼쪽 자식 노드
            build(2 * node + 2, mid + 1, end);    // 오른쪽 자식 노드
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2]; // 자식 노드 값의 합
        }
    }

    // 레이지 값을 자식 노드로 전파 (propagation)
    void propagate(int node, int start, int end) {
        if (lazy[node] != 0) {
            tree[node] += (end - start + 1) * lazy[node]; // 노드 값 업데이트
            if (start != end) {
                lazy[2 * node + 1] += lazy[node];   // 왼쪽 자식 노드에 레이지 값 전파
                lazy[2 * node + 2] += lazy[node];   // 오른쪽 자식 노드에 레이지 값 전파
            }
            lazy[node] = 0; // 레이지 값 초기화
        }
    }

    // 구간 합을 구하는 함수 (재귀)
    int query(int node, int start, int end, int left, int right) {
        propagate(node, start, end); // 레이지 값 전파
        if (right < start || end < left) { // 구간이 겹치지 않음
            return 0;
        }
        if (left <= start && end <= right) { // 구간이 완전히 포함됨
            return tree[node];
        }
        int mid = (start + end) / 2;
        int leftSum = query(2 * node + 1, start, mid, left, right);   // 왼쪽 자식 노드
        int rightSum = query(2 * node + 2, mid + 1, end, left, right); // 오른쪽 자식 노드
        return leftSum + rightSum; // 두 구간의 합 반환
    }

    // 구간 업데이트 함수 (재귀)
    void update(int node, int start, int end, int left, int right, int val) {
        propagate(node, start, end); // 레이지 값 전파
        if (right < start || end < left) { // 구간이 겹치지 않음
            return;
        }
        if (left <= start && end <= right) { // 구간이 완전히 포함됨
            tree[node] += (end - start + 1) * val; // 노드 값 업데이트
            if (start != end) {
                lazy[2 * node + 1] += val;   // 왼쪽 자식 노드에 레이지 값 전파
                lazy[2 * node + 2] += val;   // 오른쪽 자식 노드에 레이지 값 전파
            }
            return;
        }
        int mid = (start + end) / 2;
        update(2 * node + 1, start, mid, left, right, val);   // 왼쪽 자식 노드
        update(2 * node + 2, mid + 1, end, left, right, val); // 오른쪽 자식 노드
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2]; // 부모 노드 값 업데이트
    }

public:
    // 생성자: 입력 배열을 받아 세그먼트 트리를 생성
    SegmentTreeLazy(const vector<int>& inputArr) : arr(inputArr), n(inputArr.size()) {
        tree.resize(4 * n); // 트리 배열 크기 할당
        lazy.resize(4 * n, 0); // 레이지 배열 초기화
        build(0, 0, n - 1);  // 트리 구성
    }

    // 구간 합을 구하는 함수 (public)
    int query(int left, int right) {
        return query(0, 0, n - 1, left, right);
    }

    // 구간에 값을 더하는 함수 (public)
    void update(int left, int right, int val) {
        update(0, 0, n - 1, left, right, val);
    }
};

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    SegmentTreeLazy st(arr);

    // 구간 [0, 2]에 2를 더함
    st.update(0, 2, 2);

    // 구간 [1, 3]의 합
    cout << "Sum of [1, 3]: " << st.query(1, 3) << endl; // 출력: 15 (2 + 4 + 5)

    // 구간 [0, 4]의 합
    cout << "Sum of [0, 4]: " << st.query(0, 4) << endl; // 출력: 22

    return 0;
}

4) 레이지 프로퍼게이션 코드 해설

  • lazy 배열은 각 노드에 레이지 값을 저장합니다.
  • propagate() 함수는 레이지 값을 자식 노드로 전파합니다.
  • query() 함수는 쿼리 수행 전에 propagate()를 호출하여 레이지 값을 전파합니다.
  • update() 함수는 구간 업데이트 시, 해당 구간을 완전히 포함하는 노드에 lazy 값을 저장하고, 자식 노드에 대한 업데이트는 미룹니다.

5) 시간 복잡도

  • 구축 (build): O(N)
  • 쿼리 (query): O(log N) (최악의 경우 레이지 값을 전파해야 함)
  • 업데이트 (update): O(log N) (최악의 경우 레이지 값을 전파해야 함)

레이지 프로퍼게이션을 사용하면, 구간 업데이트 연산의 시간 복잡도를 O(log N)으로 유지하면서, 여러 번의 구간 업데이트 연산을 효율적으로 처리할 수 있습니다.

6. 주의사항 및 트러블 슈팅

1) 메모리 사용량

세그먼트 트리는 입력 배열의 크기보다 4배 큰 배열을 사용하므로, 메모리 사용량에 유의해야 합니다. 특히, 매우 큰 배열을 처리하는 경우, 메모리 초과(memory limit exceeded) 문제를 방지하기 위해 메모리 사용량을 고려해야 합니다.

2) 오버플로우

구간 합, 곱 등을 계산하는 경우, 정수 오버플로우에 주의해야 합니다. 데이터 타입(data type)을 적절하게 선택하거나, 오버플로우를 방지하기 위한 추가적인 처리가 필요합니다.

3) 구현 오류

세그먼트 트리 구현 시, 인덱스 계산, 재귀 호출, 구간 처리 등에서 오류가 발생하기 쉽습니다. 코드의 정확성을 검증하기 위해, 다양한 테스트 케이스를 사용하여 테스트하는 것이 중요합니다.

4) 디버깅 팁

  • 작은 테스트 케이스: 작은 크기의 입력 배열을 사용하여, 세그먼트 트리의 동작을 직접 확인합니다.
  • 출력 디버깅: 각 노드의 값, 쿼리 결과, 업데이트 결과를 출력하여, 예상과 일치하는지 확인합니다.
  • 경계 조건: 입력 배열의 크기가 0 또는 1인 경우, 또는 쿼리 구간이 비어있는 경우 등, 경계 조건에 대한 테스트를 수행합니다.

7. 결론

세그먼트 트리는 배열 기반 자료구조에 대한 구간 쿼리 문제를 해결하는 강력하고 효율적인 도구입니다. 기본적인 구조, 다양한 활용 방법, 그리고 레이지 프로퍼게이션과 같은 고급 기법을 통해, 복잡한 문제들을 효율적으로 해결할 수 있습니다. 숙련된 개발자는 세그먼트 트리를 효과적으로 활용하여, 알고리즘 성능을 최적화하고, 다양한 문제 해결 능력을 향상시킬 수 있습니다.

Coding Test의 다른 글

Coding Test
2026-02-03

2-8. 자료구조: Trie (트라이)

문자열 검색 및 관련 문제 해결에 효과적인 Trie 자료구조의 개념, 구현, 활용 예시를 설명합니다.
Coding Test
2026-02-03

2-9. 자료구조: Disjoint Set (Union-Find)

서로소 집합 (Union-Find) 자료구조와 활용
Coding Test
2026-02-03

2-11. 자료구조: Fenwick Tree (Binary Indexed Tree)

펜윅 트리 (Binary Indexed Tree)의 개념, 구현
Coding Test
2026-02-03

2-12. 자료구조: Suffix Array (접미사 배열)

접미사 배열의 개념, 구성, 활용

비슷한 글 추천

Operating System
2026-01-15

2-2. 프로세스 스케줄링 소개

프로세스 스케줄링의 목적, 종류, 평가 지표를 소개합니다. 다양한 스케줄링 알고리즘의 기초를 다룹니다.
Deep Learning
2026-01-08

3-4. 오차 역전파 (Backpropagation): 딥러닝 학습의 핵심 원리

오차 역전파 알고리즘의 원리를 수학적으로 설명하고, 다층 퍼셉트론 학습에 어떻게 적용되는지 보여줍니다.
Operating System
2026-01-20

8-2. 디스크 스케줄링

FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK 디스크 스케줄링 알고리즘을 설명하고, 성능을 비교합니다.
Deep Learning
2026-01-08

3-1. 퍼셉트론: 딥러닝의 가장 기본적인 모델

퍼셉트론의 구조와 작동 원리를 설명하고, 단층 퍼셉트론의 한계를 분석합니다.

Comments (0)

No comments yet. Be the first to comment!