[GDG - 스터디] 세그먼트 트리를 이용해 구간 합 구하기

세그먼트 트리

세그먼트 트리 ?

• 세그먼트 트리는 구간 쿼리 문제를 효율적으로 해결하기 위한 자료구조이다 ! → 특정 범위의 데이터(ex: 구간합, 구간 최소값, 최대값)를 빠르게 계산하고, 데이터가 업데이트될 경우 효율적으로 반영할 수 있다.
• 세그먼트 트리는 완전 이진 트리 형태를 가진다.
• 리프 노드 → 입력 배열의 각 요소를 표현한다.
• 내부 노드 → 특정 범위의 구간 정보를 나타낸다.
• 트리의 루트 노드는 전체 배열의 정보를 나타낸다.

---

💡 세그먼트 트리 - 구현

• 세그먼트 트리에는 3가지 핵심 연산이 있다.

트리 구성 (Build)

• 입력 배열을 기반으로 세그먼트 트리를 구성한다.
• 각 노드는 특정 범위의 값을 저장한다.

구간 쿼리 (Query)

• 특정 구간 [L, R]의 값을 계산한다.
• 현재 노드의 범위와 [L, R]의 관계에 따라 결과를 반환하거나, 자식 노드로 탐색한다.

업데이트 (Update)

• 배열 값이 변경되었을 때, 해당 값을 세그먼트 트리에 반영한다.
• 변경된 리프 노드부터 부모 노드까지 영향을 주는 노드 값을 갱신한다.

• 시간 복잡도
  • 구성 시간: $O(N)$
  • 쿼리 시간: $O(log N)$
  • 업데이트 시간: $O(log N)$
• 공간 복잡도
  • 세그먼트 트리는 입력 배열 크기의 약 4배의 공간을 사용한다 !
• 구현 과정
  1. 트리 구성
  2. 구간합 쿼리
  3. 값 업데이트

public class SegmentTree {
    private int[] tree; // 세그먼트 트리 배열
    private int[] arr;  // 입력 배열
    private int size;   // 입력 배열 크기

    // 생성자: 입력 배열을 받아 세그먼트 트리 초기화
    public SegmentTree(int[] input) {
        this.size = input.length;
        this.arr = input;
        this.tree = new int[size * 4];
        build(0, size - 1, 1); // 트리 생성
    }

    // 트리 구성
    private int build(int start, int end, int node) {
        if (start == end) { // 리프 노드
            return tree[node] = arr[start];
        }
        int mid = (start + end) / 2;
        // 왼쪽, 오른쪽 자식 노드 재귀적으로 생성
        int leftSum = build(start, mid, node * 2);
        int rightSum = build(mid + 1, end, node * 2 + 1);
        return tree[node] = leftSum + rightSum; // 구간합 저장
    }

    // 구간합 쿼리: [L, R] 범위의 합을 반환
    public int query(int L, int R) {
        return query(0, size - 1, 1, L, R);
    }

    private int query(int start, int end, int node, int L, int R) {
        if (R < start || end < L) { // 범위 밖
            return 0;
        }
        if (L <= start && end <= R) { // 범위 완전히 포함
            return tree[node];
        }
        // 겹치는 부분: 왼쪽, 오른쪽 탐색
        int mid = (start + end) / 2;
        int leftSum = query(start, mid, node * 2, L, R);
        int rightSum = query(mid + 1, end, node * 2 + 1, L, R);
        return l최치eftSum + rightSum;
    }

    // 값 업데이트: arr[index] = newValue
    public void update(int index, int newValue) {
        int diff = newValue - arr[index]; // 변경된 값 계산
        arr[index] = newValue; // 원래 배열 갱신
        update(0, size - 1, 1, index, diff);
    }

    private void update(int start, int end, int node, int index, int diff) {
        if (index < start || index > end) { // 범위 밖
            return;
        }
        tree[node] += diff; // 현재 노드 갱신
        if (start != end) { // 리프 노드가 아닌 경우
            int mid = (start + end) / 2;
            update(start, mid, node * 2, index, diff); // 왼쪽 자식
            update(mid + 1, end, node * 2 + 1, index, diff); // 오른쪽 자식
        }
   

---

문제: 최댓값과 최솟값 (백준 2357)

문제 링크

 

---

알고리즘 [접근 방법]

1. 세그먼트 트리 사용
   • 두 개의 세그먼트 트리를 구성한다.
     • 하나는 최솟값을 저장.
     • 다른 하나는 최댓값을 저장.
2. 쿼리 처리

• 각 쿼리마다 [a, b] 구간의 최소값과 최대값을 세그먼트 트리에서 계산한다.

---

해결 코드

• 세그먼트 트리는 최솟값 트리(buildMinTree)와 최댓값 트리(buildMaxTree)가 있다. → 둘다 재귀적으로 트리를 구성하였다.
• queryMin에선 범위 [a, b]에 해당하는 최소값을 반환한다. → 현재 노드의 범위와 요청 범위의 관계를 기반으로 값을 반환하거나, 자식 노드를 탐색한다.
• queryMax에서도 동일한 방식으로 범위 [a, b]에 해당하는 최대값을 반환한다.

import java.io.*;
import java.util.*;

public class Main {

    static int[] arr;
    static int[] minTree, maxTree;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken()); // 정수 개수
        int M = Integer.parseInt(st.nextToken()); // 쿼리 개수

        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // 세그먼트 트리 초기화
        minTree = new int[4 * N];
        maxTree = new int[4 * N];
        buildMinTree(0, N - 1, 1);
        buildMaxTree(0, N - 1, 1);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;

            int minValue = queryMin(0, N - 1, 1, a, b);
            int maxValue = queryMax(0, N - 1, 1, a, b);
            sb.append(minValue).append(" ").append(maxValue).append("\\n");
        }

        System.out.print(sb.toString());
    }

    // 최소값 세그먼트 트리 구성
    static int buildMinTree(int start, int end, int node) {
        if (start == end) {
            return minTree[node] = arr[start];
        }
        int mid = (start + end) / 2;
        int leftMin = buildMinTree(start, mid, node * 2);
        int rightMin = buildMinTree(mid + 1, end, node * 2 + 1);
        return minTree[node] = Math.min(leftMin, rightMin);
    }

    // 최대값 세그먼트 트리 구성
    static int buildMaxTree(int start, int end, int node) {
        if (start == end) {
            return maxTree[node] = arr[start];
        }
        int mid = (start + end) / 2;
        int leftMax = buildMaxTree(start, mid, node * 2);
        int rightMax = buildMaxTree(mid + 1, end, node * 2 + 1);
        return maxTree[node] = Math.max(leftMax, rightMax);
    }

    // 최소값 구간 쿼리
    static int queryMin(int start, int end, int node, int L, int R) {
        if (R < start || end < L) { // 범위 밖
            return Integer.MAX_VALUE;
        }
        if (L <= start && end <= R) { // 범위 완전 포함
            return minTree[node];
        }
        int mid = (start + end) / 2;
        int leftMin = queryMin(start, mid, node * 2, L, R);
        int rightMin = queryMin(mid + 1, end, node * 2 + 1, L, R);
        return Math.min(leftMin, rightMin);
    }

    // 최대값 구간 쿼리
    static int queryMax(int start, int end, int node, int L, int R) {
        if (R < start || end < L) { // 범위 밖
            return Integer.MIN_VALUE;
        }
        if (L <= start && end <= R) { // 범위 완전 포함
            return maxTree[node];
        }
        int mid = (start + end) / 2;
        int leftMax = queryMax(start, mid, node * 2, L, R);
        int rightMax = queryMax(mid + 1, end, node * 2 + 1, L, R);
        return Math.max(leftMax, rightMax);
    }
}

---

정리

• 특정 범위의 데이터(ex: 구간합, 구간 최소값, 최대값)를 계산하고 업데이트 해야할 경우엔 세그먼트 트리를 이용하자 !

 

https://thin-azimuth-2a9.notion.site/GDG-14af4ee21c0080f5889bccb29d1fa4ee?pvs=4

GDG 스터디 - 세그먼트 트리를 이용해 구간 합 구하기 | Notion