[알고리즘] Prefix sum(누적합)

만약 13부터 1억까지의 숫자 합과 2543부터 2억까지의 합의 차를 구하라는 문제가 나온다면?
일반적으로 for문을 여러 번 돌릴 것이라 생각한다.
숫자가 작을 때에는 for문을 여러번 돌려도 상관 없지만 어마어마한 큰 수가 나온다면?
for문을 1억번 돌리면 1초가 걸린다고들 한다. 만약 3억번 돌려야하면? 5억번은?
그럼 그 문제는 시간초과 난다. 그 때 사용하는 방법이 누적합이다.

누적 합(Prefix Sum, Cumulative Sum)

• 누적 합이란, 말 그대로 나열된 수의 누적된 합을 말한다.
• 조금 더 엄밀히 말하면, 수열 An에 대해서, 구간 [1, 1]의 합, 구간 [1, 2]의 합,
  구간 [1, 3]의 합, ..., [1, n]의 합을 누적 합이라고 한다.

누적 합의 사용

• 누적 합은 그 목적에 따라 다양한 문제에 활용이 가능하다.
• 대표적으로 누적 합을 사용하는 문제는 카운팅 정렬(Counting Sort), 구간 합 구하기가 존재한다.

ex 1.

arr[0]	arr[1]	arr[2]	arr[3]	arr[4]	arr[5]

arr[2] 부터 arr[5]까지의 합을 구한다고 보자.

그럼 그냥 arr[0] ~ arr[5] 까지의 합을 구한 뒤, arr[0]부터 arr[1]까지의 합을 빼주면 된다.

시간을 절약할 수 있다.

ex 2.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        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());
        int[] arr = new int[N+1];
        int[] accumulate = new int[N+1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            accumulate[i] = accumulate[i-1] + arr[i];// 누적합
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int answer = accumulate[end] - accumulate[start-1];
            sb.append(answer).append("\n");
        }

        System.out.println(sb.toString());
    }
}