[백준] 2042번 구간 합 구하기

문제 설명

https://www.acmicpc.net/problem/2042

문제 풀이

• 세그먼트 트리 자료구조를 적용하면 바로 해결되는 문제이다.

소스 코드 (JAVA)

import java.io.*;

public class Main {

    public static class SegmentTree{
        private long[] tree;

        // 생성자에서 세그먼트 트리의 전체노드 수 계산하여 메모리 할당
        SegmentTree(int n) {
            double height = Math.ceil(Math.log(n)/Math.log(2)) + 1;
            long nodeCnt = Math.round(Math.pow(2, height));
            tree = new long[Math.toIntExact(nodeCnt)];
        }

        //세그먼트 트리의 노드 값 초기화
        long init(long[] arr, int node, int start, int end) {
            int mid = (start + end) / 2;
            //트리의 리프노드인 경우
            if (start == end) return tree[node] = arr[start];
            // 리프노드가 아닌 경우에는 자식노드 값을 더해서 노드의값 초기화
            else {
                return tree[node] = init(arr, node*2, start, mid)
                        + init(arr, node*2+1, mid+1, end);
            }
        }

        // 배열의 특정 구간 합을 세그먼트 트리로 구하기
        long sum(int node, int start, int end, int left, int right) {
            // 노드가 가지는 값의 구간이 구하려고 하는 합의 구간에 속하지 않는 경우 0리턴
            if (end < left || right < start) return 0;
            // 노드가 가지는 값이 구간이 구하려고 하는 합이랑 일치하는 경우 노드값 리턴
            else if (left <= start && right >= end) return tree[node];
            // 다음 2가지 경우 자식노드를 탐색해서 값을 리턴
            // 1. 노드가 가지는 값의 구간이 구하려고 하는 합의 구간에 일부는 속하고 일부는 안속할때
            // 2. 노드가 가지는 값의 구간이 구하려고 하는 합의 구간을 모두 포함하는 경우
            else return sum(node*2, start, (start+end)/2, left, right)
                + sum(node*2+1, (start+end)/2+1, end, left, right);
        }

        //배열의 특정 인덱스 값이 변경될 경우 세그먼트 트리의 노드 값 변경
        long update(int node, int start, int end, int index, long changeValue) {
            //노드가 가지는 값의 구간에 배열의 변경될 인덱스가 포함안될 경우
            if (index < start || end < index) return tree[node];
            //노드가 가지는 값의 구간과 배열의 변경될 인덱스값이 같은 경우
            else if (start == index && end == index) return tree[node] = changeValue;
            //노드가 가지는 값의 구간에 배열의 변경될 인덱스값이 포함되는 경우 자식 노드를 탐색후 리턴
            else return tree[node] = update(node*2, start, (start+end)/2, index, changeValue)
                + update(node*2+1, (start+end)/2+1, end, index, changeValue);
        }
    }

    public static String[] info;
    public static String[] oper;
    public static long[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        info = br.readLine().split(" ");
        arr = new long[Integer.parseInt(info[0])+1];
        for (int i = 1; i <= Integer.parseInt(info[0]); i++)
            arr[i] = Long.parseLong(br.readLine());

        //세그먼트 트리 초기화
        SegmentTree st = new SegmentTree(Integer.parseInt(info[0]));
        st.init(arr, 1, 1, Integer.parseInt(info[0]));

        for (int i = 0; i < Integer.parseInt(info[1]) + Integer.parseInt(info[2]); i++) {
            oper = br.readLine().split(" ");

            //배열의 특정 인덱스 값을 변경하는 경우
            if (Integer.parseInt(oper[0]) == 1) {
                st.update(1, 1, Integer.parseInt(info[0]), Integer.parseInt(oper[1]), Long.parseLong(oper[2]));
            }
            //배열의 특정 구간 합 구하기
            else {
                long result = st.sum(1, 1, Integer.parseInt(info[0]), Integer.parseInt(oper[1]), Integer.parseInt(oper[2]));
                bw.write(result + "\n");
            }
        }
        br.close();
        bw.flush();
        bw.close();
    }
}