003. 구간 합 구하기4(백준11659번)

문제

문제 분석하기

시간 제한 1초 = 1억번의 연산안에 해결되야한다.

$1 <= N <= 100,000$ and $1<= M <= 100,000$

최대치로 생각해봤을때 100,000개의 구간의 합을 매번 계산한다..? 1초만에 계산을 끝낼 수 없을것 같다.

그렇다면? 구간 합 개념을 적용해보자!(개념의 자세한 내용은 추후 포스트)
합배열 : $S[i] = S[i-1] + A[i]$
$A[0]$ 부터 $A[i]$ 까지의 합

구간합 : $S[j] - S[i-1]$
i 에서 j 까지의 구간 합

슈도코드 작성

long 숫자개수 저장;
long 질의개수 저장;
long 대상배열 선언;
long[] 합배열 선언;

for(i < 숫자 개수) {
	대상 배열의 요소 입력받기;
	합배열 초기화;
}

for(i < 질의 개수) {
	질의 입력받기;
	구간합 출력하기;
}

코드구현

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() );  
       
       long Numbers = Long.parseLong( st.nextToken() );  
       long queryCnt = Long.parseLong( st.nextToken() );  
       long[] sumArr = new long[ ( int )Numbers + 1];  
       
       st = new StringTokenizer( br.readLine() );  
       for ( int i = 1; i <= Numbers; i++ ) {  
          sumArr[ i ] =  sumArr[ i - 1 ] + Long.parseLong(st.nextToken() );  
          }
       
       for ( int j = 0; j < queryCnt; j++ ) {  
          st = new StringTokenizer( br.readLine() );  
          long a = Long.parseLong( st.nextToken() );  
          long z = Long.parseLong( st.nextToken() );  
          bw.write( ( int )(sumArr[ ( int )z ] - sumArr[ ( int )(a - 1) ]) +  "\n");  
          }  
         
       bw.flush();  
       bw.close();  
    }  
} // end