[BOJ - JAVA] - 구간 합 구하기4 (세그먼트 트리)

# 주소

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

11659번: 구간 합 구하기 4

# 문제

# 문제 해설 및 코드리뷰

import java.awt.*;
import java.util.*;
public class Main {
    static int n,m;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        int arr[] = new int[n+1];
        for(int i = 1; i <= n; i++){
            arr[i] = arr[i-1] + scan.nextInt();
        }
        while(m--> 0){
            int x = scan.nextInt();
            int y = scan.nextInt();
            System.out.println(arr[y] - arr[x-1]);
        }
    }
}

세그먼트 트리가 어떤건지 궁금해서 단계별로 풀어보려고 제일 쉬운거먼저 풀었습니다.

처음엔 arr를 입력받고 그것들을 정상적으로 구간 인덱스에 맞는것들을 다 더해서 제출했는데 시간초과가 뜨더라고요.

그래서 조금 고민을 했습니다.

Buffer를 이용해서 입력을 받을까??? 하다가 입력문과는 전혀 관계 없을 것 같아서 생각을 조금 바꾸었습니다.

arr를 입력받을 때 arr[i-1]에다가 새로 입력받는걸 더해서 arr를 만들면 굳이 구간마다 arr를 더해서 sum을 만드는 일은 필요 없겠더라고요.

그래서 arr를 arr[i] = arr[i-1] + scan.nextInt();로 받고 이것을 구간에 맞게 출력하면 정답이 되실겁니다.

감사합니다.