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

문제:
수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력:
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력:
총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제출:

import java.io.IOException;
import java.util.Scanner;

public class Bj_11659 {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		int[] arr = new int[n+1];
		int[] sum = new int[n+1];
		for (int i=1; i<=n; i++) {
			arr[i] = sc.nextInt();
			sum[i] = sum[i-1] + arr[i];
		}
		
		for (int i=0; i<m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			sb.append(sum[b]-sum[a-1] + "\n");
		}
		System.out.print(sb);
	}
}

누적 합 문제는 입력받는 숫자배열에 들어가는 값이 바뀌지 않는다는 점을 이용해야 한다.
배열이 변하지 않으니 구간의 합도 변하지 않는다.
arr배열에 수를 입력받을 때 sum배열에도 구간의 합을 저장해준다.

sum[b] = arr[1]+...+arr[b];
sum[a-1] = arr[1]+...+arr[a-1];
sum[b] - sum[a-1] = arr[a]+...+arr[b]; // (1≤i≤j≤N)

예를 들어 a=3, b=5이면 arr[3]+arr[4]+arr[5]의 값을 구해야 하는데
sum[b] = arr[1]+...+arr[5] 이고, sum[a-1] = arr[1]+...+arr[2]이므로
sum[b] - sum[a-1]을 하면 sum[b] - sum[a-1] = arr[3]+...+arr[5]라는 원하는 답이 나온다.