Segment Tree

1. 알고리즘 동작 과정

1. 트리 구성
• 배열을 기반으로 트리를 만들며, 보통 크기를 4 * N 정도로 잡음.
• 리프 노드는 배열의 값들을 그대로 저장.
• 내부 노드는 리프 노드에서 올라오며 구간 정보를 저장.

2. 구간 조회 (Range Query)
• 구하고자 하는 범위가 노드의 범위와 일치하면 값을 그대로 반환.
• 일부만 겹칠 경우 왼쪽, 오른쪽 자식 노드로 재귀적으로 탐색.

3. 값 갱신 (Update)
• 특정 인덱스의 값을 변경할 때 리프 노드에서 시작하여 부모 노드까지 값을 갱신.

2. 시간 복잡도

3. 주로 사용되는 곳

• 구간 합, 구간 최소/최대값 구하기

• 온라인 쿼리 문제 (구간 질의가 반복되는 문제)

• 문자열 처리 (구간에 대한 정보 저장 시)

• Lazy Propagation과 함께 사용해 구간 갱신 문제 해결

4. 예시코드 (자바)

// 세그먼트 트리로 구간 합을 처리하는 예시
class SegmentTree {
    int[] tree;
    int[] arr;
    int size;

    // 생성자
    public SegmentTree(int[] input) {
        this.size = input.length;
        this.arr = input;
        this.tree = new int[size * 4]; // 트리 배열의 크기 설정
        build(1, 0, size - 1); // 루트노드: 1, 범위: 0~size-1
    }

    // 트리 구성 함수
    private int build(int node, int start, int end) {
        if (start == end) {
            // 리프 노드
            return tree[node] = arr[start];
        }
        int mid = (start + end) / 2;
        int left = build(node * 2, start, mid); // 왼쪽 자식
        int right = build(node * 2 + 1, mid + 1, end); // 오른쪽 자식
        return tree[node] = left + right; // 구간 합 저장
    }

    // 구간 합 조회 함수
    public int query(int left, int right) {
        return query(1, 0, size - 1, left, right);
    }

    private 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 lSum = query(node * 2, start, mid, left, right); // 왼쪽 합
        int rSum = query(node * 2 + 1, mid + 1, end, left, right); // 오른쪽 합
        return lSum + rSum;
    }

    // 값 갱신 함수 (arr[idx] = value)
    public void update(int idx, int value) {
        update(1, 0, size - 1, idx, value);
    }

    private int update(int node, int start, int end, int idx, int value) {
        if (idx < start || idx > end) return tree[node]; // 해당 노드 범위가 아니면 종료

        if (start == end) {
            // 리프 노드 갱신
            return tree[node] = value;
        }

        int mid = (start + end) / 2;
        int left = update(node * 2, start, mid, idx, value);
        int right = update(node * 2 + 1, mid + 1, end, idx, value);
        return tree[node] = left + right; // 내부 노드 갱신
    }
}

출력 예시

int[] arr = {1, 3, 5, 7, 9, 11};
SegmentTree st = new SegmentTree(arr);

// [1~3] 구간합: 3 + 5 + 7 = 15
System.out.println(st.query(1, 3));

// 값 변경: arr[1] = 10
st.update(1, 10);

// 다시 조회: 10 + 5 + 7 = 22
System.out.println(st.query(1, 3));

5. 장점과 단점

✅ 장점

• 다양한 구간 연산 처리 가능 (합, 최소, 최대, XOR 등)

• 트리 구조로 빠른 시간에 쿼리 및 갱신 처리 가능

• 배열 기반으로 구현해 효율적 메모리 사용 가능

❌ 단점

• 구현이 복잡하고 디버깅이 어려움

• 메모리를 최대 4배 이상 사용

• 단순히 전체합/전체갱신만 필요할 경우엔 오버킬이 될 수 있음