[백준/트리] 2042번 구간 합 구하기 (JAVA)

문제

---

풀이

설명

initTree()

• arr 값을 기반으로 tree의 1번 노드부터 리프 노드까지 재귀적으로 초기화한다.
• start == end이면 리프 노드이기 때문에 tree에 arr 값을 저장하고 caller에 이 값을 전달한다.
• callee는 왼쪽과 오른쪽 자식 노드의 값을 받아 그 합을 현재 노드인 node에 저장한다.

updateTree()

• targetIndex: 갱신하려는 값의 arr에서의 인덱스값
• newValue: 갱신하려는 값

• targetIndex를 포함하고 있는 node가 아닌 경우 값을 갱신하지 않는다.
• 값을 갱신할 때는 기존의 arr 값을 빼고 새 값을 더한다.
• start == end이면 리프 노드이기 때문에 추가로 자식 노드를 갱신하지 않고 리턴한다.
• 왼쪽과 오른쪽 자식 노드를 재귀 호출하여 갱신한다.

sum()

• start, end: node가 포함하는 값의 범위
• left, right: 합을 구하고자 하는 범위

합을 구할 때는 3가지 경우로 나누어 생각할 수 있다.

1. left-right와 start-end가 전혀 겹치지 않는 경우
   → 현재 node 값이 쓸모없으므로 0 반환
2. left-right가 start-end를 완전히 포함하는 경우
   → 현재 node 값이 유효하므로 값 반환
3. left-right와 start-end가 부분적으로 겹치는 경우
   → 반으로 나눠 재귀 호출하여 유효한 값만 재탐색

삽질의 원인

1. 배열은 Long으로 잘 선언해놓고, input을 파싱할 때 Integer로 파싱했다.
2. 값을 변경할 때 tree만 변경하고 arr 값을 변경하지 않았다.

꼼꼼히 조건을 확인하자..

코드

import java.io.*;

public class Main {

    private static final int MAX = 1000000;
    private static final int UPDATE = 1;
    private static final int PICK = 2;

    private static long[] arr = new long[MAX + 1];
    private static long[] tree = new long[(MAX + 1) * 4];

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

        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);
        int k = Integer.parseInt(line[2]);
        for (int i = 1; i <= n; i++) arr[i] = Long.parseLong(br.readLine());
        initTree(1, 1, n);

        for (int i = 0; i < m + k; i++) {
            line = br.readLine().split(" ");
            int a = Integer.parseInt(line[0]);
            int b = Integer.parseInt(line[1]);
            long c = Long.parseLong(line[2]);

            if (a == UPDATE) {
                updateTree(1, 1, n, b, c);
                arr[b] = c;
            } else if (a == PICK)
                bw.append(String.valueOf(sum(1, 1, n, b, (int) c))).append("\n");
        }

        br.close();
        bw.close();
    }

    private static long initTree(int node, int start, int end) {
        if (start == end) return tree[node] = arr[start];
        int mid = (start + end) / 2;
        return tree[node] = initTree(node * 2, start, mid)
                + initTree(node * 2 + 1, mid + 1, end);
    }

    private static void updateTree(int node, int start, int end, int targetIndex, long newValue) {
        if (targetIndex < start || targetIndex > end) return;
        tree[node] -= arr[targetIndex];
        tree[node] += newValue;
        if (start == end) return;

        int mid = (start + end) / 2;
        updateTree(node * 2, start, mid, targetIndex, newValue);
        updateTree(node * 2 + 1, mid + 1, end, targetIndex, newValue);
    }

    private static long sum(int node, int start, int end, int left, int right) {
        if (left > end || right < start) return 0;
        if (start >= left && 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);
    }
}