백준 2042번 구간 합 구하기(JAVA)

백준 2042번 구간 합 구하기

https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

문제

어떤 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보다 작거나 같은 정수이다.

출력

첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.

---

소스 코드

- 인덱스트리/세그먼트트리 기본 문제

- 인덱스트리를 좋아해서 인덱스트리로 풀었음

- 인덱스트리 연산 시 long 타입 사용 필요

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    private static int N, M, K, leafCnt;
    private static long[] indexedTree;
    //-2^63보다 크거나 같고, 2^63-1보다 작거나 같은 정수 => long
    //-2^31보다 크거나 같고, 2^31-1보다 작거나 같은 정수 => int
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        leafCnt = 1;
        while (leafCnt < N) {
            leafCnt *= 2;
        }
        //for문 쓰려면 이렇게 : for (leafCnt = 1; leafCnt < N; leafCnt *= 2);

        indexedTree = new long[leafCnt*2];
        leafCnt = leafCnt - 1;
        /*이렇게 해두면 i 번째 리프노트의 값을 구할 때,
        indexedTree[leafCnt + i] 로 구할 수 있다
        즉 리프 노드 중 세 번째의 값을 원하면 indexedTree[leafCnt + 3]을 하면 됨 */

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

        init(leafCnt+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(leafCnt + b, c);
            }else{
                long sum = query(leafCnt + b, (int) (leafCnt + c));
                bw.write(sum + "\n");
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
    //인덱스트리
    public static void init(int start, int end) {
        for (int i = start; i < start + end; i++) {
            int idx = i / 2;
            while (idx != 0) {
                indexedTree[idx] += indexedTree[i];
                idx /= 2;
            }
        }
    }

    public static void update(int idx, long val) {
        // 기존 값과 새로운 값의 차이만큼 더해준다.
        val -= indexedTree[idx];
        while (idx != 0) {
            indexedTree[idx] += val;
            idx /= 2;
            //비트 연산 : idx >>= 1
        }
    }
    public static long query(int start, int end) {
        long result = 0;
        while (start < end) {
            //start가 홀수 : right 노드
            if(start % 2 == 1) result += indexedTree[start];
            //end가 짝수 : left 노드
            if(end % 2 == 0) result += indexedTree[end];
            //상위 노드로 이동
            start = (start + 1) / 2;
            end = (end - 1) / 2;
            //비트 연산 사용하려면 : start = (start + 1) >> 1;
        }
        if(start == end) result += indexedTree[start];
        return result;
    }
}