[JAVA] 백준 11659번

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

11659번: 구간 합 구하기 4

 

💡  매 구간마다 더할 필요가 없다. 누적합을 이용!

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N, M, i, j;
    static int[] sum;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        // 누적합
        sum = new int[N+1];
        sum[0] = 0;
        st = new StringTokenizer(br.readLine());
        for(int x=1; x<=N; x++) {
            sum[x] = sum[x-1] + Integer.parseInt(st.nextToken());
        }
        
        // 구간합
        for(int x=0; x<M; x++) {
            st = new StringTokenizer(br.readLine());
            
            i = Integer.parseInt(st.nextToken());
            j = Integer.parseInt(st.nextToken());
            
            sb.append(sum[j] - sum[i-1] + "\n");
        }
        
        System.out.println(sb);
 
    }
 
}