[BOJ] 2042번 구간 합 구하기 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M, K;

    static long[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        // 배열 입력
        arr = new long[N + 1];
        for (int i = 1; i <= N; i++) {
            arr[i] = Long.parseLong(br.readLine());
        }
        // 세그먼트 트리 생성 및 초기화
        SegmentTree segmentTree = new SegmentTree(N);
        segmentTree.init(arr, 1, 1, N);
        // 연산 입력
        for (int i = 0; i < M + K; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            long c = Long.parseLong(st.nextToken());

            if (a == 1) {
                // update
                segmentTree.update(1, 1, N, b, c - arr[b]);
                arr[b] = c;
            } else if (a == 2) {
                // sum
                sb.append(segmentTree.sum(1, 1, N, b, (int) c)).append("\n");
            }
        }
        System.out.println(sb);
    }

    static class SegmentTree {
        long[] tree;
        int treeSize;

        public SegmentTree(int size) {
            int h = (int) Math.ceil(Math.log(size) / Math.log(2));
            this.treeSize = (int) Math.pow(2, h + 1);
            tree = new long[treeSize];
        }

        public long init(long[] arr, int node, int start, int end) {
            // leaf 노드 -> 원소 배열의 값을 그대로 담음
            if (start == end) return tree[node] = arr[start];
            // leaf 노드가 아닌 경우 자식 노드의 합을 담음
            return tree[node] = init(arr, node * 2, start, (start + end) / 2)
                    + init(arr, node * 2 + 1, (start + end) / 2 + 1, end);
        }

        public void update(int node, int start, int end, int idx, long diff) {
            // 변경할 index 값이 범위를 벗어나면 확인할 필요가 없음
            if (idx < start || idx > end) return;
            // 원래 데이터 값과 변경 데이터의 차이저장 (현재 노드에 대한 수행)
            tree[node] += diff;
            // 리프노드가 아니면 자식노드들에 대해서도 수행
            int mid = (start + end) / 2;    // 중간 인덱스
            if (start != end) {
                update(node * 2, start, mid, idx, diff);
                update(node * 2 + 1, mid + 1, end, idx, diff);
            }
        }

        public long sum(int node, int start, int end, int left, int right) {
            // 범위를 벗어나면 0 반환
            if (left > end || right < start) return 0;
            // 구간이 완전히 일치하는 경우
            if (left <= start && end <= right) return tree[node];
            // 구간이 한쪽만 겹치거나 완전히 포함하는 경우
            int mid = (start + end) / 2;
            return sum(node*2, start, mid, left, right)
                    + sum(node*2+1, mid+1, end, left, right);
        }
    }
}

📄 해설

• 세그먼트 트리를 이용해서 풀어야하는 문제. 세그먼트 트리에 대한 자세한 설명이 필요하다면 작성자의 글을 참고해도 좋고, 아래 글을 참고해도 좋음.
  작성자의 글
  작성자가 참고했던 글
• 값을 입력받고, 세그먼트 트리를 생성하고, 초기화함
• a, b, c 를 입력받아 update 연산과 sum 연산을 각각 수행해주면 됨. sum 연산은 수행시 마다 StringBuilder 에 넣어 결과 출력을 세팅함
• 각각의 연산은 세그먼트 트리 객체의 update 메소드와 sum 메소드를 호출하여
• 세그먼트 트리를 구현해서 해당 메소드들을 사용하는 문제이므로, 세그먼트 트리에 대한 설명 외엔 해줄 수 있는 것이 없으니, 세그먼트 트리를 잘 공부하길 바람