[Java] 백준 11659번 구간 합 구하기 4

구간합을 구하는 문제입니다.
수열이 주어지고 i~j까지의 수의 합을 출력하면 됩니다.

수열의 길이는 최대 10만이며 구간합은 최대 10만번 구해야합니다.
구간합을 매번 구해주게 되면은 시간초과가 발생하게 됩니다.

이를 해결하기 위해 누적합을 사용합니다.
차례대로 누적합을 구해줍니다.
구하려고 하는 a~b의 구간합을 구하기 위해서
b까지의 구간합 - (a-1)까지의 구간합을 계산해주었습니다.

sum[b] - sum[a-1]

코드

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

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.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[] arr = new int[n+1];
		int[] sum = new int[n+1];
		st = new StringTokenizer(br.readLine());
		arr[1] = Integer.parseInt(st.nextToken());
		sum[1] = arr[1];
		for(int i=2; i<=n; ++i) {
			arr[i] = Integer.parseInt(st.nextToken());
			sum[i] = sum[i-1] + arr[i];
		}
		for(int i=1; i<=m; ++i) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			System.out.println(sum[b] - sum[a-1]) ;
		}
	}
}