BOJ 2042 구간 합 구하기 [Java]

문제

BOJ 2042 구간 합 구하기

접근방법

• 음 내가 느끼기에는 이 문제는 자료구조 쪽의 스택, 큐 스탠다드 문제처럼 인덱스트리에 대한 기본적인 문제인 것 같다.
• 그래서 오랫동안의 고민이나 기발한 발상이 아닌 그냥 개념 공부 여부에 따를 것이다.
• 인덱스 트리(세그먼트 트리)가 처음에는 되게 낯설게 느껴졌었는데 조금씩 해보니까 오히려 편하다는 생각이 가끔 들 정도이다.
• 자세한 개념에 대한 이야기는 생략한다. 능력과 시간이 된다면 따로 게시글을 작성,,

구현

import java.io.*;
import java.util.*;

// Indexed Tree 활용

class Main {
    static long[] tree;
    static long[] nums;
    static int N, M, K, S;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ", false);

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        nums = new long[N+1];

        for (int i = 1; i <= N; i++) {
            nums[i] = Long.parseLong(br.readLine());
        }

        S = 1;
        while (S<N) S*=2;
        tree = new long[S*2];
        init(1, N, 1);
        //init();

        for (int i = 0; i < M+K; i++) {
            st = new StringTokenizer(br.readLine(), " ", false);
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            long c = Long.parseLong(st.nextToken());


            if (a == 1) {
                // b번째 수를 c로 바꾸기
                long diff = c- nums[b];
                nums[b] = c;
                update(1, N, 1, b, diff);


            } else {
                // b번째 수부터 c번째 수까지의 합
                System.out.println(query(1, N, 1, b, (int) c));
            }

        }

    }

    public static long init(int start, int end, int node) {
        if (start == end)
            return tree[node] = nums[start];

        int mid = (start + end) / 2;

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


    static long query(int left, int right, int node, int start, int end) {
        if (end < left || right < start) return 0;
        else if (start <= left && right <= end) return tree[node];
        else {
            int mid = (left + right) / 2;
            long leftNode = query(left, mid, node*2, start, end);
            long rightNode = query(mid + 1, end, node*2 + 1, start, end );
            return leftNode + rightNode;
        }
    }



    static void update(int left, int right, int node,int target, long diff) {
        if (target < left || right < target) return;

        else {
            tree[node] += diff;
            if (left != right) {
                int mid = (left + right) / 2;
                update(left, mid, node*2, target, diff);
                update(mid+1, right, node*2+1, target, diff);
            }
            else return;
        }

    }
}

제출