[백준 온라인 저지] 11659. 구간 합 구하기 4

1. 입력

- 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다.

- 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다.

- 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

- 1 ≤ N ≤ 100,000

- 1 ≤ M ≤ 100,000

- 1 ≤ i ≤ j ≤ N

 

2. 출력

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

 

3. 예제

 

4. 코드

import java.util.*;
import java.io.*;
class Main {
    static int n;
    static int[] tree;
    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 token = new StringTokenizer(br.readLine());
        n = Integer.valueOf(token.nextToken());
        int m = Integer.valueOf(token.nextToken());
        int[] nums = new int[n+1];
        tree = new int[n+1];
        token = new StringTokenizer(br.readLine());
        for(int i=1 ; i<=n ; i++)
            nums[i] = Integer.valueOf(token.nextToken());
        for(int i=1 ; i<=n ; i++)
            update(i, nums[i]);
        for(int i=0 ; i<m ; i++){
            token = new StringTokenizer(br.readLine());
            bw.write(getPart(Integer.valueOf(token.nextToken()),Integer.valueOf(token.nextToken()))+"\n");
        }    
        bw.flush(); bw.close();
    }
    
    static void update(int i, int dif) {
        while(i<=n) {
            tree[i] += dif;
            i += (i&-i);
        }
    }

    static int sum(int i) {
        int ans = 0;
        while(i>0) {
            ans += tree[i];
            i -= (i&-i);
        }
        return ans;
    }
	
    static int getPart(int a, int b) {
        return sum(b) - sum(a-1);
    }
}

- 60696KB, 692ms