Segment Tree(구간 합 구하기)

백준 : 2042

tree의 update가 일어나면 구간 합을 구해 출력하는 문제

import java.io.*;

/*
 * 구간합 구하기 : 백준(2042)
 * main : 입출력
 * build : tree 생성
 * update : 값 업데이트
 * query : 구간 합 쿼리
 * N : 노드의 개수
 * M : update 횟수
 * K : 구간합을 구하는 횟수
 */

public class intervalSum {
    static int N, M, K;
    static long[] ar;
    static long[] tree;

    static void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = ar[start];
        } else {
            int mid = (start + end) / 2;

            build(node * 2, start, mid);
            build(node * 2 + 1, mid + 1, end);
            tree[node] = tree[node * 2] + tree[node * 2 + 1];
        }
    }

    static long query(int node, int start, int end, int l, long r) {
        if (r < start || end < l) {
            return 0;
        }
        if (l <= start && end <= r) {
            return tree[node];
        }

        int mid = (start + end) / 2;
        long left = query(node * 2, start, mid, l, r);
        long right = query(node * 2 + 1, mid + 1, end, l, r);
        return left + right;
    }

    static void update(int node, int start, int end, int idx, long value) {
        if (start == end) {
            ar[idx] = value;
            tree[node] = value; // 리프 노드 값 변경
        } else {
            int mid = (start + end) / 2;
            if (idx <= mid) {
                update(node * 2, start, mid, idx, value);
            } else {
                update(node * 2 + 1, mid + 1, end, idx, value);
            }
            tree[node] = tree[node * 2] + tree[node * 2 + 1]; // 부모 갱신
        }
    }

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

        String[] firstLine = br.readLine().split(" ");
        N = Integer.parseInt(firstLine[0]);
        M = Integer.parseInt(firstLine[1]);
        K = Integer.parseInt(firstLine[2]);

        ar = new long[N];
        int h = Integer.highestOneBit(N); // highestOneBit : 정수에서 가장 왼쪽에 있는 1비트의 위치에 1을 가진 정수를 반환하는 메서드
        if (h < N) {
            h <<= 1;
        }

        int size = h * 2;
        tree = new long[size];

        for (int i = 0; i < N; i++) {
            ar[i] = Long.parseLong(br.readLine());
        }
        build(1, 0, N - 1);

        for (int i = 0; i < M + K; i++) {
            String[] queryLine = br.readLine().split(" ");
            int type = Integer.parseInt(queryLine[0]);
            int b = Integer.parseInt(queryLine[1]);
            long c = Long.parseLong(queryLine[2]);
            if (type == 1) {
                update(1, 0, N - 1, b - 1, c);
            } else if (type == 2) {
                long output = query(1, 0, N - 1, b - 1, c - 1);
                bw.write(output + "\n");
            }
        }

        bw.flush();
        bw.close();
        br.close();

    }
}