구간 합 구하기

문제

문제 설명

어떤 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)번째 수까지의 합을 구하여 출력하면 된다.

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

입출력 예

입력	출력
5 2 2
1
2
3
4
5
1 3 6
2 2 5
1 5 2	17
2 3 5	12

제출 코드

import java.io.*;

// https://www.acmicpc.net/problem/2042
public class one2042 {
    static private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static private BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public void solution() throws IOException {
        String[] line = reader.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]); // 변경이 일어나는 횟수
        int k = Integer.parseInt(line[2]); // 구간합을 구하는 횟수
        m += k;
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(reader.readLine());
        }
        // 트리 만들기
        int height = (int) Math.ceil(Math.log(n) / Math.log(2));
        int size = (1 << (height + 1));
        long[] tree = new long[size];
        init(arr, tree, 1, 0, n - 1);

        for (int i = 0; i < m; i++) {
            line = reader.readLine().split(" ");
            int type = Integer.parseInt(line[0]);
            if (type == 1) { // 수 변경
                int index = Integer.parseInt(line[1]) - 1;
                long val = Long.parseLong(line[2]);
                update(arr, tree, 1, index, val, 0, n - 1);

            } else { // 구간합
                int left = Integer.parseInt(line[1]) - 1;
                int right = Integer.parseInt(line[2]) - 1;
                writer.write(query(tree, 1, 0, n - 1, left, right) + "\n");
            }
        }
        writer.flush();
    }

    private void update(long[] arr, long[] tree, int node, int index, long val, int start, int end) {
        if (index < start || index > end) return;
        if (start == end) {
            arr[index] = val;
            tree[node] = val;
            return;
        } else {
            update(arr, tree, node * 2, index, val, start, (start + end) / 2);
            update(arr, tree, node * 2 + 1, index, val, (start + end) / 2 + 1, end);
            tree[node] = tree[node * 2] + tree[node * 2 + 1];
        }
    }

    private long query(long[] tree, int node, int start, int end, int left, int right) {
        if (left > end || right < start) {
            return 0;
        } else if (left <= start && end <= right) {
            return tree[node];
        } else {
            long leftSum = query(tree, node * 2, start, (start + end) / 2, left, right);
            long rightSum = query(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right);
            return leftSum + rightSum;
        }
    }

    private void init(long[] arr, long[] tree, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            init(arr, tree, 2 * node, start, (start + end) / 2); // 오른쪽
            init(arr, tree, 2 * node + 1, (start + end) / 2 + 1, end); // 왼쪽
            tree[node] = tree[node * 2] + tree[node * 2 + 1];
        }
    }

    public static void main(String[] args) throws IOException {
        new one2042().solution();
    }
}