Prefix Sum(누적 합) 알고리즘이란?

Prefix Sum(누적 합) 알고리즘은 배열의 앞에서부터 차례대로 합을 미리 구해두고,
이 누적된 합을 이용해서 어떤 구간의 합이든 빠르게 계산하는 방법이다.

이 알고리즘의 가장 큰 장점은 누적 합을 만드는 데는 O(N) 한 번, 그 이후 구간 합을 구하는 질의는 각각 O(1)의 시간 복잡도를 가지기에 총 시간 복잡도는 O(N)으로, 배열은 그대로인데 구간 합을 여러 번 물어보는 문제에서 유리하다.

Prefix Sum의 기본 아이디어

길이가 N인 배열 arr가 있다고 할 때, 다음과 같이 누적 구간합을 정의한다.

prefix[i] = arr[1]+arr[2]+⋯+arr[i] (1≤i≤N)

i	1	2	3	4	5
arr[i]	5	4	3	2	1
prefix[i]	5	9	12	14	15

만약 구간 3부터 5까지의 합을 구하고 싶다면, prefix[5] - prefix[2]를 구하면 되기에 arr[3]부터 arr[5]까지 일일이 더하는게 아니기에 시간복잡도는 O(1)이 된다.

한 번만 구간의 합을 물어본다면 당연히 O(N)의 시간복잡도를 사용해서 구간합을 미리 구해둘 필요가 없이 바로 arr에서 더하면 되겠지만, 만약 여러 번 구간의 합을 물어본다면 O(N)이 아닌 O(N * M)으로 시간 복잡도가 증가하기에 처음 구간합을 구하는데 필요한 O(N)만 구한다면 이후로는 O(1)의 시간복잡도만 사용하는 구간합을 사용하는 것이 매우 유리하다.

추가적으로 1차원 배열이 아닌 2차원 배열(행렬)에서도 활용이 가능하다.

Prefix Sum 알고리즘의 적용 예시

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

public class boj_11659_S3 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        String[] temp = br.readLine().split(" ");

        int[] arr = new int[N];

        // O(N)
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(temp[i]);
        }

        int[] prefixSum = new int[N+1];

        prefixSum[0] = 0;

        // O(N) -> 구간 합 계산
        for (int i = 1; i < N+1; i++) {
            prefixSum[i] = prefixSum[i-1] + arr[i-1];
        }

        // O(M)
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            sb.append(prefixSum[end] - prefixSum[start - 1]).append('\n');
        }

        System.out.println(sb);

        br.close();
    }
}

핵심
1 ≤ N ≤ 100,000
1 ≤ M ≤ 100,000
1 ≤ i ≤ j ≤ N

이 문제의 제한 사항을 보면 N과 M이 모두 100,000까지 가능하다.

이 문제를 단순하게 sum으로 배열들의 합을 계속 구하게 되면 O(N * M)으로 10,000,000,000으로 시간초과가 나기에 O(N) 알고리즘 또는 O(NlogN)알고리즘으로 풀어야 한다고 접근을 하고 시작을 하는 것이 좋다.

그 중에서 이 문제는 배열은 그대로인데 구간 합을 여러 번 물어보는 문제이기에 O(N) 알고리즘은 구간합 알고리즘을 채택하여 문제 풀이를 하면 좋다고 생각을 하게 되는 것이다.