[백준] 2042 - 구간 합 구하기 (자바 Java) : 세그먼트 트리

[Gold I] 구간 합 구하기 - 2042

문제 링크

성능 요약

메모리: 348124 KB, 시간: 1936 ms

분류

세그먼트 트리(segtree), 자료 구조(data_structures)

문제 설명

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b(1 ≤ b ≤ N)번째 수를 c로 바꾸고 a가 2인 경우에는 b(1 ≤ b ≤ N)번째 수부터 c(b ≤ c ≤ N)번째 수까지의 합을 구하여 출력하면 된다.

입력으로 주어지는 모든 수는 -2⁶³보다 크거나 같고, 2⁶³-1보다 작거나 같은 정수이다.

출력

첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -2⁶³보다 크거나 같고, 2⁶³-1보다 작거나 같은 정수이다.

 

---

https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%AC-Segment-Tree

[자료구조] 세그먼트 트리 (Segment Tree)

세그먼트 트리에 대해서는 처음 알았는데, 구간합을 구할 때 유용한 자료구조였다.

이진트리의 성질을 이용해서 왼쪽 자식, 오른쪽 자식으로 분기를 계속하며 구간합을 저장해두는 자료구조이다.

 

세그먼트 트리를 연습할 수 있는 문제였는데, 입력 범위가 2^63이어서, int가 아니라 long으로 입력을 받아야 한다.

그리고 update를 할 때 tree에서만 update를 하고 배열의 값을 update해주지 않아서 틀렸었다.

그 외에는 세그먼트 트리의 성질을 활용하면 풀 수 있는 문제였다

package BOJ.Gold.g1;

import java.util.Scanner;

public class BOJ_2042_구간합구하기 {
    static int N, M, K;
    static long[] tree;
    static long[] arr;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        K = sc.nextInt();
        tree = new long[N * 4];
        arr = new long[N + 1];
        for (int i = 1; i <= N; i++)
            arr[i] = sc.nextLong();
        // 구간합 구하기
        init(1, N, 1);

        for (int i = 0; i < (M + K); i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            if (a == 1) {
                // 변경
                long c = sc.nextLong();
                update(1, N, 1, b, arr[b], c);
                arr[b] = c;
            } else {
                // 구간합 구하기
                int c = sc.nextInt();
                sb.append(getSum(1, N, 1, b, c)).append("\n");
            }
        }
        System.out.print(sb);
    }

    static long init(int start, int end, int index) {
        // start부터 end까지의 값을 tree[index]에 담음
        if (start == end) return tree[index] = arr[start]; // start==end면 해당 index값을 저장
        int mid = (start + end) / 2;
        tree[index] = init(start, mid, index * 2) + init(mid + 1, end, index * 2 + 1);
        // 트리의 왼쪽에는 start~mid까지의 합, 오른쪽은 mid+1~end까지의 합
        return tree[index];

    }

    /**
     * start: 시작 구간
     * end: 끝 구간
     * index: 구간합을 저장한 tree의 index
     * updateIdx: 값을 바꿀 배열의 index
     * oldValue: 바꿀 값의 원래 값
     * newValue: 바꿀 값
     */
    static void update(int start, int end, int index, int updateIdx, long oldValue, long newValue) {
        if (updateIdx < start || updateIdx > end) {
            // 범위 밖 -> 변경x
            return;
        }
        tree[index] -= oldValue;
        tree[index] += newValue;

        if (start == end) return;
        int mid = (start + end) / 2;
        update(start, mid, index * 2, updateIdx, oldValue, newValue);
        update(mid + 1, end, index * 2 + 1, updateIdx, oldValue, newValue);
    }

    /**
     * start, end: index에 저장된 구간합의 범위
     * left, right: 구하려고 하는 구간합
     */
    static long getSum(int start, int end, int index, int left, int right) {
        if (left > end || right < start) return 0; // 범위밖
        if (left <= start && right >= end) return tree[index];  // 범위 안에 있는 경우 해당 구간합 return
        int mid = (start + end) / 2;
        return getSum(start, mid, index * 2, left, right) + getSum(mid + 1, end, index * 2 + 1, left, right);
    }

}