백준 구간 합 구하기 문제(세그먼트트리)

백문문제링크

이름이 구간합으로 되어있길래 구간합으로 풀리는 문제인줄 알았다

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

public class Main {
	
	public static void main(String args[]) throws IOException {
		Scanner sc = new Scanner(System.in);
        // 배열의 길이
        int N = sc.nextInt();
        // 수의 변경이 일어나는 횟수
        int M = sc.nextInt();
        // 구간합을 구하는 횟수
        int K = sc.nextInt();
        //원본배열
        long[] arr = new long[N];
        
        // 원본 배열 입력
        for(int i=0;i<N;i++){
            arr[i] = sc.nextLong();
        }
        for(int i=0;i<M+K;i++){
            //구간합 배열 만듬
            long[] arr2=new long[N+1];
            long a = sc.nextLong();
            long b = sc.nextLong();
            long c = sc.nextLong();
            if(a==1){
                arr[(int)(b-1)]=c;
            }else{
                // 구간합 배열 만듬
                for(int j=1;j<=N;j++){
                    arr2[j] = arr2[j-1]+arr[j-1];
                }
                System.out.println(arr2[(int)c]-arr2[(int)(b-1)]);
            }
        }
	}
}

문제의 입력 조건이 long형이라 int형으로는 풀수 없으며,for문이 이중으로 들어가서 연산횟수가 2억을 훨씬 넘어버린다.찾아보니 세그먼트트리라는걸 사용해야한다 하더라.아직 배우지 않은 내용이다.배우고 다시 도전해야겠다