[백준] 2042번 구간 합 구하기 (gold 1

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

class SegTree{

    long[] tree;

    public SegTree(int n) {
        int height = (int) Math.ceil(Math.log(n) / Math.log(2));
        int treeSize =(int)Math.pow(2,height+1);
        tree = new long[treeSize];
    }

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

    public void update(int node, int start, int end, int index, long diff){
        if(index<start || end<index){
            return;
        }

        tree[node]+=diff;

        if(start!=end){
            update(node*2, start, (start+end)/2 , index ,diff);
            update(node*2+1, (start+end)/2+1, end, index, diff);
        }
    }

    public long sum(int node, int start, int end, int left, int right){
        if(right<start || end<left){
            return 0;
        }
        if(left<=start && end<=right){
            return tree[node];
        }

        return sum(node*2, start, (start+end)/2, left, right)+
                sum(node*2+1, (start+end)/2+1, end, left, right);
    }
}

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=new StringTokenizer(br.readLine());

        int n=Integer.valueOf(st.nextToken());
        int m=Integer.valueOf(st.nextToken());
        int k=Integer.valueOf(st.nextToken());

        //수 저장할 배열
        long[] arr=new long[n+1];
        for(int i=1; i<=n; i++){
            arr[i]=Long.valueOf(br.readLine());
        }

        SegTree seg=new SegTree(n);
        seg.init(1,arr,1,n);

        //쿼리 진행하기.
        for(int i=1; i<=k+m; i++){
            st=new StringTokenizer(br.readLine());
            //변형 쿼리
            if(Integer.valueOf(st.nextToken())==1){
                int b=Integer.valueOf(st.nextToken());
                long c=Long.valueOf(st.nextToken());
                seg.update(1,1,n,b,c-arr[b]);
                //해당 지점에 또다시 변경이 일어날 수 있으므로 값을 바꾸어 주어야 함.
                arr[b]=c;
            }
            //구간합 쿼리
            else{
                int b=Integer.valueOf(st.nextToken());
                int c=Integer.valueOf(st.nextToken());
                bw.write(seg.sum(1,1,n,b,c)+"\n");
            }
        }
        bw.flush();
    }
}