[알고리즘] 38. 누적합(Prefix Sum)

[알고리즘] 38. 누적합(Prefix Sum)

지난 글에서는 슬라이딩 윈도우에 대해 정리했습니다. 이번 글에서는 배열의 구간 합을 빠르게 구할 때 자주 사용하는 누적합(Prefix Sum)에 대해 알아보겠습니다.

누적합은 배열의 앞에서부터 현재 위치까지의 합을 미리 저장해두는 방법입니다. 이렇게 미리 합을 저장해두면 특정 구간의 합을 매번 반복문으로 다시 계산하지 않고 빠르게 구할 수 있습니다.

누적합은 배열의 앞에서부터 합을 미리 저장해두고, 원하는 구간의 합을 빠르게 구하는 알고리즘 기법입니다.

---

1. 누적합이란?

누적합은 이름 그대로 값을 계속 누적해서 더한 결과입니다. 예를 들어 아래 배열이 있다고 하겠습니다.

배열: [1, 2, 3, 4, 5]

앞에서부터 누적해서 더하면 다음과 같습니다.

1
1 + 2 = 3
1 + 2 + 3 = 6
1 + 2 + 3 + 4 = 10
1 + 2 + 3 + 4 + 5 = 15

따라서 누적합 배열은 다음과 같습니다.

누적합: [1, 3, 6, 10, 15]

이 배열을 만들어두면 특정 구간의 합을 빠르게 계산할 수 있습니다.

누적합은 “처음부터 여기까지의 합”을 미리 저장해두는 방식입니다.

---

2. 누적합이 필요한 이유

배열에서 여러 구간의 합을 반복해서 구해야 하는 문제를 생각해보겠습니다.

배열: [1, 2, 3, 4, 5]

1번 구간: 2번부터 4번까지의 합
2번 구간: 1번부터 5번까지의 합
3번 구간: 3번부터 5번까지의 합

매번 반복문으로 구간을 직접 더하면 구간의 길이만큼 시간이 걸립니다. 질문이 많아질수록 계산량도 커집니다.

하지만 누적합 배열을 미리 만들어두면 각 구간 합을 거의 한 번의 계산으로 구할 수 있습니다.

구간 합을 여러 번 구해야 한다면 누적합을 먼저 떠올리면 좋습니다.

---

3. 누적합 배열 만들기

가장 기본적인 누적합 배열을 만들어보겠습니다.

int[] arr = {1, 2, 3, 4, 5};

int[] prefix = new int[arr.length];

prefix[0] = arr[0];

for (int i = 1; i < arr.length; i++) {
    prefix[i] = prefix[i - 1] + arr[i];
}

for (int value : prefix) {
    System.out.print(value + " ");
}

출력 결과는 다음과 같습니다.

1 3 6 10 15

prefix[i]는 arr[0]부터 arr[i]까지의 합을 의미합니다.

인덱스	arr 값	prefix 값	의미
0	1	1	1
1	2	3	1 + 2
2	3	6	1 + 2 + 3
3	4	10	1 + 2 + 3 + 4
4	5	15	1 + 2 + 3 + 4 + 5

---

4. 1번 인덱스부터 사용하는 누적합

알고리즘 문제에서는 구간이 보통 1번부터 주어지는 경우가 많습니다. 예를 들어 “2번부터 4번까지의 합”처럼 표현됩니다.

이럴 때는 누적합 배열을 n + 1 크기로 만들고, 1번 인덱스부터 사용하는 방식이 편합니다.

int[] arr = {1, 2, 3, 4, 5};
int n = arr.length;

int[] prefix = new int[n + 1];

for (int i = 1; i <= n; i++) {
    prefix[i] = prefix[i - 1] + arr[i - 1];
}

for (int i = 1; i <= n; i++) {
    System.out.print(prefix[i] + " ");
}

출력 결과는 다음과 같습니다.

1 3 6 10 15

여기서 prefix[0]은 0으로 둡니다. 이렇게 하면 구간 합 공식을 더 깔끔하게 사용할 수 있습니다.

구간 합 문제에서는 prefix[0] = 0으로 두고 1번 인덱스부터 사용하는 방식이 자주 쓰입니다.

---

5. 구간 합 공식

누적합의 핵심은 구간 합 공식입니다. 1번 인덱스 기준으로 left부터 right까지의 합은 다음과 같이 구합니다.

구간 합 = prefix[right] - prefix[left - 1]

예를 들어 배열이 다음과 같다고 하겠습니다.

배열:    1  2  3  4  5
인덱스:  1  2  3  4  5
누적합:  1  3  6 10 15

2번부터 4번까지의 합을 구하려면 다음처럼 계산합니다.

2번부터 4번까지의 합 = 2 + 3 + 4 = 9

prefix[4] = 10
prefix[1] = 1

prefix[4] - prefix[1] = 10 - 1 = 9

즉 2번부터 4번까지의 합은 prefix[4]에서 1번까지의 합을 빼면 됩니다.

left부터 right까지의 합은 prefix[right]에서 prefix[left - 1]을 빼면 됩니다.

---

6. 구간 합 Java 코드

누적합으로 특정 구간의 합을 구하는 코드는 다음과 같습니다.

int[] arr = {1, 2, 3, 4, 5};
int n = arr.length;

int[] prefix = new int[n + 1];

for (int i = 1; i <= n; i++) {
    prefix[i] = prefix[i - 1] + arr[i - 1];
}

int left = 2;
int right = 4;

int sum = prefix[right] - prefix[left - 1];

System.out.println(sum);

출력 결과는 다음과 같습니다.

9

2번부터 4번까지의 값은 2, 3, 4이고 합은 9입니다.

---

7. 여러 구간 합 빠르게 구하기

누적합은 구간 합을 여러 번 구해야 할 때 특히 강력합니다.

배열: [1, 2, 3, 4, 5]

질문 1: 1번부터 3번까지의 합
질문 2: 2번부터 5번까지의 합
질문 3: 3번부터 4번까지의 합

누적합 배열을 한 번 만들어두면 각 질문은 공식 하나로 처리할 수 있습니다.

int[][] queries = {
    {1, 3},
    {2, 5},
    {3, 4}
};

for (int[] query : queries) {
    int left = query[0];
    int right = query[1];

    int sum = prefix[right] - prefix[left - 1];

    System.out.println(sum);
}

출력 결과는 다음과 같습니다.

6
14
7

각 구간의 합은 다음과 같습니다.

• 1번부터 3번까지: 1 + 2 + 3 = 6
• 2번부터 5번까지: 2 + 3 + 4 + 5 = 14
• 3번부터 4번까지: 3 + 4 = 7

---

8. 완전탐색과 누적합 비교

구간 합을 매번 반복문으로 계산하면 구간 길이만큼 시간이 걸립니다. 질문이 많아지면 매우 비효율적입니다.

완전탐색으로 구간 합을 구하면 다음과 같습니다.

int sum = 0;

for (int i = left; i <= right; i++) {
    sum += arr[i];
}

이 방식은 구간 길이가 길수록 오래 걸립니다. 반면 누적합을 사용하면 구간 합을 한 번의 계산으로 구할 수 있습니다.

방식	전처리	구간 합 1번 계산
반복문 직접 합산	없음	O(N)
누적합	O(N)	O(1)

질문이 한두 개라면 반복문도 괜찮을 수 있습니다. 하지만 구간 합 질문이 많다면 누적합이 훨씬 효율적입니다.

누적합은 O(N) 전처리 후 구간 합을 O(1)에 구할 수 있습니다.

---

9. 누적합 시간복잡도

누적합의 시간복잡도는 전처리와 질의 처리로 나누어 생각할 수 있습니다.

작업	시간복잡도
누적합 배열 만들기	O(N)
구간 합 한 번 구하기	O(1)
구간 합 M번 구하기	O(M)
전체	O(N + M)

N개의 배열에 대해 누적합을 만들고, M개의 구간 합 질문을 처리하면 전체 시간복잡도는 O(N + M)입니다.

반복문으로 매번 직접 합을 구하면 최악의 경우 O(N × M)이 될 수 있으므로 차이가 매우 큽니다.

---

10. 0번 인덱스 기준 누적합

0번 인덱스 기준으로도 누적합을 사용할 수 있습니다. 다만 구간의 시작이 0일 때는 따로 처리해야 합니다.

int[] arr = {1, 2, 3, 4, 5};
int[] prefix = new int[arr.length];

prefix[0] = arr[0];

for (int i = 1; i < arr.length; i++) {
    prefix[i] = prefix[i - 1] + arr[i];
}

int left = 1;
int right = 3;

int sum;

if (left == 0) {
    sum = prefix[right];
} else {
    sum = prefix[right] - prefix[left - 1];
}

System.out.println(sum);

위 코드는 0번 인덱스 기준에서 left부터 right까지의 합을 구합니다.

하지만 구간 합 문제에서는 1번 인덱스 기준으로 prefix[0] = 0을 두는 방식이 더 깔끔한 경우가 많습니다.

입문 단계에서는 prefix 배열을 n + 1 크기로 만들고 1번 인덱스부터 사용하는 방식을 추천합니다.

---

11. 음수가 있어도 누적합을 사용할 수 있을까요?

누적합은 배열에 음수가 있어도 사용할 수 있습니다. 단순히 앞에서부터 합을 저장하는 방식이기 때문입니다.

배열: [3, -2, 5, -1]

누적합:
3
3 + (-2) = 1
1 + 5 = 6
6 + (-1) = 5

음수가 있어도 prefix[right] - prefix[left - 1] 공식은 그대로 사용할 수 있습니다.

구간 합 = prefix[right] - prefix[left - 1]

다만 슬라이딩 윈도우의 일부 가변 길이 방식은 음수가 섞이면 적용하기 어려울 수 있습니다. 반면 누적합은 음수 여부와 상관없이 구간 합 계산에 사용할 수 있습니다.

---

12. long을 사용해야 하는 경우

누적합 문제에서는 합이 int 범위를 넘을 수 있습니다. 배열의 값이 크거나 원소 개수가 많다면 long을 사용하는 것이 안전합니다.

원소 하나가 1,000,000
원소 개수가 100,000개

전체 합 = 100,000,000,000

이 값은 int 범위를 넘습니다. 따라서 누적합 배열을 long[]으로 만들어야 합니다.

long[] prefix = new long[n + 1];

for (int i = 1; i <= n; i++) {
    prefix[i] = prefix[i - 1] + arr[i - 1];
}

누적합은 값이 계속 더해지므로 int 범위를 넘을 가능성을 항상 확인해야 합니다.

---

13. 2차원 누적합 맛보기

누적합은 1차원 배열뿐 아니라 2차원 배열에서도 사용할 수 있습니다. 2차원 누적합은 특정 직사각형 영역의 합을 빠르게 구할 때 사용합니다.

1 2 3
4 5 6
7 8 9

예를 들어 왼쪽 위부터 특정 위치까지의 합을 미리 저장해두면, 나중에 어떤 직사각형 구간의 합도 빠르게 계산할 수 있습니다.

2차원 누적합은 식이 조금 더 복잡하므로 이번 글에서는 개념만 소개하고, 이후 구간합 문제에서 더 자세히 다루겠습니다.

2차원 누적합은 표나 지도에서 특정 직사각형 영역의 합을 빠르게 구할 때 사용합니다.

---

14. 누적합이 사용되는 대표 문제

누적합은 아래와 같은 문제에서 자주 사용됩니다.

문제 유형	설명
구간 합 질의	left부터 right까지의 합을 여러 번 구함
연속 부분합	특정 구간의 합을 빠르게 계산
평균 계산	구간 합을 구한 뒤 길이로 나눔
2차원 영역 합	표에서 직사각형 구간의 합을 계산
변화량 누적	구간에 더해지는 값을 누적해서 처리

문제를 보고 “구간의 합을 여러 번 구해야 한다”는 느낌이 들면 누적합을 먼저 고려하면 좋습니다.

---

15. 누적합에서 자주 하는 실수

누적합 문제를 풀 때는 아래 실수를 조심해야 합니다.

• prefix 배열 크기를 n + 1로 만들지 않아 인덱스가 꼬이는 경우
• arr[i]와 prefix[i]의 인덱스 차이를 헷갈리는 경우
• 구간 합 공식에서 prefix[left - 1]을 빼지 않는 경우
• left가 1일 때 prefix[0]을 사용하는 구조를 이해하지 못하는 경우
• 0번 인덱스 기준과 1번 인덱스 기준을 섞어서 사용하는 경우
• 합이 int 범위를 넘을 수 있는데 int[]를 사용하는 경우
• 누적합을 만들어야 하는데 매번 반복문으로 구간을 다시 더하는 경우

특히 아래 공식을 정확히 기억해야 합니다.

1번 인덱스 기준:
left부터 right까지의 합 = prefix[right] - prefix[left - 1]

누적합 실수는 대부분 인덱스 기준과 구간 합 공식에서 발생합니다.

---

16. 정리

이번 글에서는 누적합에 대해 정리했습니다.

• 누적합은 배열의 앞에서부터 현재 위치까지의 합을 미리 저장하는 방법이다.
• prefix[i]는 보통 앞에서부터 i번째까지의 합을 의미한다.
• 1번 인덱스 기준에서는 prefix[0]을 0으로 둔다.
• left부터 right까지의 합은 prefix[right] - prefix[left - 1]로 구한다.
• 누적합 배열은 O(N)에 만들 수 있다.
• 구간 합 한 번은 O(1)에 구할 수 있다.
• 구간 합 질문이 많을 때 매우 효율적이다.
• 합이 커질 수 있는 문제에서는 long[]을 고려해야 한다.

누적합은 구간 합 문제의 기본이 되는 중요한 기법입니다. 처음에는 인덱스가 헷갈릴 수 있지만, prefix[0]을 0으로 두고 1번 인덱스 기준으로 생각하면 훨씬 안정적으로 사용할 수 있습니다.

누적합의 핵심은 합을 미리 저장해두고, 구간 합을 뺄셈 한 번으로 빠르게 구하는 것입니다.

---

다음 글 예고

다음 글에서는 구간합 문제를 본격적으로 정리하겠습니다.

1차원 구간 합, 여러 개의 구간 질의, 2차원 구간 합, 누적합을 적용해야 하는 문제 패턴을 예제로 정리해보겠습니다.