백준 2042 구간합 JAVA

인풋이 워낙 크다보니 단순한 반복으론 못푸는 문제이다.
구간합을 세그먼트 트리를 이용하여 저장하는 방식이다.
세그먼트 트리는 이진 탐색을 이용해 사전에 트리에 구간의 합을 저장해 놓고
그 구간의 합을 재활용 하는 식으로 구현이 된다.

자세한 구현 방법은 다음 문제에서 자세히 설명하도록 하겠다.

package com.company;
import java.io.*;
import java.util.*;

//아래 함수에서 start는 구간의 시작을 의미. end는 구간의 끝을 의미.
class SegTree{
    long arr[];
    long tree[];

    SegTree(long[] arr){
        this.arr=arr;
        this.tree=new long[arr.length*4];
    }

    public long init(int start, int end, int node){
        if(start==end){
            return tree[node]=arr[start];
        }
        int mid=(start+end)/2;
        return tree[node]=init(start,mid,node*2)+init(mid+1,end,node*2+1);
    }

    public long sum(int start, int end, int node, long left, long right){
        if(start>right||end<left)
            return 0;
        if(start>=left&&end<=right){
            return tree[node];
        }
        int mid=(start+end)/2;
        return sum(start,mid,node*2,left,right)+sum(mid+1,end,node*2+1,left,right);
    }

    public void update(int start, int end,int node,int index, long changNum){
        if(start>index||end<index)
            return;
        tree[node]+=changNum;//바꾸고자하는 인덱스의 요소와
        if(start!=end){
            int mid=(start+end)/2;
            update(start,mid,node*2,index,changNum);
            update(mid+1,end,node*2+1,index,changNum);
        }
    }
}

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

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        long[] arr = new long[N];

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

        SegTree tree = new SegTree(arr);
        tree.init(0,N-1,1);

        for(int i=0;i<M+K;i++){
            st=new StringTokenizer(br.readLine());
            int operator = Integer.parseInt(st.nextToken());
            if(operator==1){
                int index = Integer.parseInt(st.nextToken());
                long changeNum = Integer.parseInt(st.nextToken());
                tree.update(0,N-1,1,index-1,changeNum-tree.arr[index-1]);
                tree.arr[index-1]=changeNum;
            }else if(operator==2){
                int left = Integer.parseInt(st.nextToken());
                int right = Integer.parseInt(st.nextToken());
                bw.write(Long.toString(tree.sum(0,N-1,1,left-1,right-1)));
                bw.newLine();
            }
        }

        bw.flush();
        bw.close();
    }
}