구간 합 배열은 i번째 인덱스에 있는 값이 i번째 전의 모든 인덱스에 해당하는 값에 i번째 인덱스에 해당하는 값을 넣는 것.
선언하는 방식 ==> S[ i ] = S[ i - 1 ] + A [ i ]
위의 합 배열만 잘 활용하면 무난하게 풀 수 있는 문제이다.
import java.io.*;
import java.util.*;
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());
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
long[] sumArr = new long[N + 1];
for(int i = 1; i <= N; i++) {
sumArr[i] = sumArr[i - 1] + Integer.parseInt(st.nextToken());
}
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int I = Integer.parseInt(st.nextToken());
int J = Integer.parseInt(st.nextToken());
sb.append(sumArr[J] - sumArr[I - 1] + "\n");
}
System.out.println(sb);
}
}