[JAVA] 백준 2042 : 구간 합 구하기

문제

2042번: 구간 합 구하기

 

해결방법

안녕하세요 !

글은 쓰고 있지 않지만 꾸준히 알고리즘을 풀이하고는 있는데 최근에 세그먼트 트리를 하게 되면서 기본 구조를 알 수 있는 문제는 기록을 해두면 좋을 것 같아서 오랜만에 글을 작성해 봅니다.

 

세그먼트 트리는 누적합의 다음 형태라고 볼 수 있는데

누적합의 경우 구간의 합은 O(1)에 구해지지만 중간에 값이 업데이트가 될 경우 O(N)만큼 시간이 소모되기 때문에 업데이트 횟수가 많다면 사용하기 부적합합니다.

이를 대체하기 위해 세그먼트 트리를 사용하는데 세그먼트 트리는 업데이트와 구간합 모두 O(logN)에 가능하기 때문에 훨씬 효율적이라고 할 수 있습니다.

 

자세한 설명은 여기 블로그에 소개가 잘 되어있으니 참고해 주세요.

저도 오랜만에 세그먼트 트리를 보다보니 코드가 잘 생각이 안나서 참고하면서 풀었습니다.

[Java] 세그먼트 트리(Segment Tree)

---

이 문제는 위에서 설명한 세그먼트 트리를 활용하는 기초적인 문제라고 볼 수 있는데 특이사항으론 주어지는 수의 범위가 2의 63 제곱까지여서 long을 사용해주셔야 합니다.

자세한 내용은 코드를 보면서 확인해 주세요 !

 

코드

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

public class bj_2042 {
    static final int CHANGE = 1;
    static final int SUM = 2;

    static int N;
    static long[] number;
    static long[] segmentTree;

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

        number = new long[N + 1];
        for (int i = 1; i <= N; i++) {
            number[i] = Long.parseLong(br.readLine());
        }

        segmentTree = new long[(N + 1) * 4];
        makeTree(1, N, 1);

        for (int i = 0; i < M + K; i++) {
            st = new StringTokenizer(br.readLine());
            int mode = Integer.parseInt(st.nextToken());

            if (mode == CHANGE) {
                int id = Integer.parseInt(st.nextToken());
                long newNumber = Long.parseLong(st.nextToken());

                updateTree(1, N, 1, id, newNumber - number[id]);
                number[id] = newNumber;
            } else if (mode == SUM) {
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                if (a < b)
                    System.out.println(getSum(1, N, 1, a, b));
                else
                    System.out.println(getSum(1, N, 1, b, a));
            }
        }
    }

    static long makeTree(int start, int end, int index) {
    	// 모든 구간 완료시 종료
        if (start == end) return segmentTree[index] = number[start];

        int mid = (start + end) / 2;
        return segmentTree[index] = makeTree(start, mid, index * 2) + makeTree(mid + 1, end, index * 2 + 1);
    }

    static void updateTree(int start, int end, int index, int id, long value) {
    	// 범위에서 벗어나면 종료
        if (id < start || id > end) return;

        // 범위에 포함되면 값을 변경
        segmentTree[index] += value;
        if (start == end) return; // 트리 제일 아래까지 탐색완료시 종료

        int mid = (start + end) / 2;
        updateTree(start, mid, index * 2, id, value);
        updateTree(mid + 1, end, index * 2 + 1, id, value);
    }

    static long getSum(int start, int end, int index, int left, int right) {
        if (right < start || left > end) return 0; // 범위에서 벗어나면 종료
        if (left <= start && right >= end) return segmentTree[index]; // 범위를 포함하고 있으면 값을 리턴

        int mid = (start + end) / 2;
        return getSum(start, mid, index * 2, left, right) + getSum(mid + 1, end, index * 2 + 1, left, right);
    }
}