2042. 구간 합 구하기

과거에 통과했던 문젠데 재채점을 하면서 `틀렸습니다!`로 바뀌었다.

 

세그먼트 트리를 이용한 풀이였던 것으로 기억하는데.. 일단 최대 최소값이 각각 8바이트의 정수값을 가진다.

 

 

 

 

 

 

과거에도 그렇고 이번에도 그렇고 많이 고통받은 문제다.  

재채점에서 틀렸습니다를 받은 이유를 살펴보니 c의 입력이 int값을 넘어선 값을 받을수도 있지만, 기존에는 int로 해놔서 그런걸로 밝혀졌다..

 

 

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static int N, M, K;
    public static BigInteger ans;
    public static BigInteger[] arr;

    public static void Solve() throws IOException {
        BufferedReader br = null;
        BufferedWriter bw = null;
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        K = Integer.parseInt(stk.nextToken());

        int level = (int) (Math.log10(N - 1) / Math.log10(2));
        arr = new BigInteger[(int) Math.pow(2, level + 2)];

        Arrays.fill(arr, BigInteger.ZERO);

        int Leaf = (int) Math.pow(2, level + 1);
        // 리프노드의 시작좌표

        for (int i = 0; i < N; i++) {
            stk = new StringTokenizer(br.readLine(), " ");
            arr[Leaf + i] = new BigInteger(stk.nextToken());
            update(Leaf + i);
        }// 첫 입력과 동시에 세그먼트 트리 초기화

        for (int i = 0, a, b; i < M + K; i++) {
            BigInteger c;
            stk = new StringTokenizer(br.readLine(), " ");
            a = Integer.parseInt(stk.nextToken());
            b = Integer.parseInt(stk.nextToken());
            c = new BigInteger(stk.nextToken());

            if (a == 1) {
                arr[Leaf + b - 1] = c;
                update(Leaf + b - 1);
            } else {
                ans = SumOfSection(1, Leaf, Leaf * 2 - 1, Leaf + b - 1, Leaf + c.intValue() - 1);
                bw.write(ans + "\n");
            }
        }

        bw.flush();
    }

    public static BigInteger SumOfSection(int node, int start, int end, int left, int right){
        if(end < left || start > right) return BigInteger.ZERO;

        if(left <= start && end <= right) return arr[node];

        int mid = start + (end - start) / 2;
        return SumOfSection(node*2, start, mid, left, right).add(SumOfSection(node*2 + 1, mid + 1, end, left, right));
    }

    public static void update(int leaf) {
        if(leaf == 1) return;

        arr[leaf/2] = leaf % 2 == 0 ? arr[leaf].add(arr[leaf + 1]) : arr[leaf].add(arr[leaf - 1]);
        update(leaf/2);
    }


    public static void main(String[] args) throws IOException {
        Solve();
    }
}