1) 문제 분석하기

문제에서 수의 개수와, 합을 구해야 하는 횟수는 최대 100000

→ 일일이 다 더하면 시간 제한 0.5초를 지킬 수 없음.

구간합을 구해야 하는 배열의 길이가 100000개짜리라고 가정하고 질의 횟수도 100000개라고 하면

→ 질의 1번에 최악의 케이스이면 100000번의 연산이 이뤄짐.

2) 손으로 풀어보기

1. N개의 수를 입력받음과 동시에 합 배열을 생성

   S[i] = S[i-1] + A[i]

2. 구간 i ~ j가 주어지면 구간 합을 구하는 공식으로 정답 출력

   S[i] - S[i-1]

인덱스 0번째는 없다고 생각하고 그대로 진행하면 됨!

3) 슈도코드 작성하기

suNo(숫자 개수), quizNo(질의 개수) 저장하기
for (숫자 개수만큼 반복하기) {
	합 배열 생성하기(S[i] = S[i-1] + A[i])
}
for (질의 개수만큼 반복하기) {
	질의 범위 받기(i ~ j)
	구간 합 출력하기 (S[j] - S[i-1])
}

4) 실제 코드 작성하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] s = new int[n+1];

        for (int i = 1; i <= n; i++) {
            s[i] = s[i-1] + Integer.parseInt(st.nextToken());
        }

        StringBuilder sb = new StringBuilder();
        for (int line = 0; line < m; line++) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            sb.append(s[j] - s[i-1]).append("\n");
        }
        System.out.println(sb);
    }
}