[백준 5568] 구간 합 구하기 4 (Java) [누적합]

문제

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

11659번: 구간 합 구하기 4

 

알고리즘

누적합

 

풀이

1. 1~N 각각 자기 자신까지의 합을 구한다

2. from~to까지의 누적합을 구한다. (aSum[to] - aSum[from-1]

 

코드

package com.company;

import java.io.*;
import java.util.StringTokenizer;

public class Test_Accumulate_Sum {

    public static int N, M;
    public static int[] aSum;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        aSum = new int[N + 1];

        st = new StringTokenizer(bf.readLine());
        for (int i = 1; i <= N; i++) {
            aSum[i] = aSum[i-1] + Integer.parseInt(st.nextToken());
        }


        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(bf.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            sb.append(aSum[to] - aSum[from - 1] + "\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}