[백준] 구간 합 구하기 4 java

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

11659번: 구간 합 구하기 4

 

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

이므로 시간복잡도 O(N)이 되어야합니다.

 

문제 풀이 :

N배열이 5 4 3 2 1일 때, 배열의 합들을 누적해서 0 5 9 12 14 15 로 만들어줍니다.

i번째 수부터 j번째 수까지 합은 arr[j] - arr[i-1]이 됩니다.

import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] arr = new int[N+1];
		
		for(int i = 1; i<= N; i++) {
			int x = sc.nextInt();
			arr[i] = arr[i-1]+x;
		}
		
		for(int i = 0; i<M; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			
			System.out.println(arr[y]-arr[x-1]);
			
		}
		
	}
}