구간합

도입

구간합 알고리즘의 핵심은 배열을 미리 전처리해 여러 번의 구간 합 질의를 빠르게 처리하는 것이며, 그 대표 해법이 누적합(prefix sum)이다

구간합은 배열에서 l부터 r까지의 합을 반복해서 물어보는 문제를 뜻합니다. 이런 질의를 매번 반복문으로 직접 더하면 한 번의 질의마다 선형 시간이 걸리지만, 누적합 배열을 미리 만들어 두면 훨씬 빠르게 처리할 수 있습니다.

:contentReference[oaicite:0]{index=0}

특히 배열이 변하지 않는 정적 배열이고, 구간 합을 여러 번 물어보는 상황에서는 누적합이 거의 정석처럼 쓰입니다. Princeton의 설명처럼 이 기법의 핵심은 한 번 전처리한 뒤 부분 구간 합을 상수 시간에 꺼내는 데 있습니다.

:contentReference[oaicite:1]{index=1}

필요성

구간합을 잘 다루면 O(NQ)로 터지는 문제를 O(N+Q) 수준까지 줄일 수 있어서 코딩테스트에서 체감 효율 차이가 매우 크다

USACO Guide는 정적 구간합 문제에서, 질의마다 직접 더하면 전체가 O(NQ)가 되지만 누적합을 쓰면 O(N) 전처리 뒤 각 질의를 O(1)에 처리해 전체를 O(N+Q)로 만들 수 있다고 설명합니다. 즉, 구간합은 단순한 테크닉이 아니라 시간 복잡도를 근본적으로 바꾸는 전처리 패턴입니다.

:contentReference[oaicite:2]{index=2}

구간합이 특히 강한 문제 유형

• 정적 배열에서 다수의 합 질의 처리
• 특정 구간의 평균 / 합 / 부분합 비교
• 부분 배열 합이 특정 값이 되는 경우 세기
• 좌우 균형 비교 문제
• 2차원 격자의 직사각형 합 질의

:contentReference[oaicite:3]{index=3}

정의

누적합은 각 위치까지의 합을 미리 저장해 두는 배열이고, 구간합은 그 누적값의 차이로 계산한다

누적합 배열은 각 인덱스까지의 합을 저장합니다. USACO Guide는 1-indexed 기준에서 prefix[k]를 1부터 k까지의 합으로 정의하고, 이를 prefix[k] = prefix[k - 1] + arr[k]로 선형 시간에 만들 수 있다고 설명합니다.

:contentReference[oaicite:4]{index=4}

이렇게 만든 누적합 배열이 있으면 구간 [L, R]의 합은 전체 앞부분 합에서 왼쪽 바깥 부분을 빼는 방식으로 얻을 수 있습니다. 1-indexed 기준 설명에서는 prefix[R] - prefix[L - 1], prefix[0] = 0을 두는 n + 1 배열 방식에서는 prefix[right + 1] - prefix[left]가 됩니다.

:contentReference[oaicite:5]{index=5}

핵심 원리

구간합이 빠른 이유는 새로운 합을 계산하는 것이 아니라, 이미 저장해 둔 두 누적값의 차이만 읽기 때문이다

Princeton과 USACO 설명을 요약하면, 누적합은 “배열을 한 번 끝까지 읽어 합을 누적 저장하는 비용 O(N)”을 먼저 지불하고, 이후에는 질의마다 두 칸만 읽어서 답을 만드는 구조입니다. 그래서 질의가 많을수록 이득이 커집니다.

:contentReference[oaicite:6]{index=6}

arr = [a0, a1, a2, a3, ...] prefix[i] = a0 + a1 + ... + ai

구간합(l, r) = prefix[r] - prefix[l - 1]
또는
구간합(l, r) = prefix[r + 1] - prefix[l]

기본 구현

실전에서는 보통 prefix[0] = 0 을 두는 n+1 길이 배열 방식이 가장 실수하기 적다

AlgoMaster는 prefix[0] = 0을 두는 n + 1 방식이 왼쪽 경계가 0일 때의 예외 처리를 없애 준다고 설명합니다. 그래서 코딩테스트에서는 이 방식이 가장 자주 쓰입니다.

:contentReference[oaicite:7]{index=7}

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

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

int l = 1;
int r = 3;
long sum = prefix[r + 1] - prefix[l]; // arr[1] + arr[2] + arr[3]

실전 팁

합이 커질 수 있는 문제에서는 int보다 long으로 누적합 배열을 만드는 편이 안전합니다. 구간합 문제는 인덱스보다 합의 범위 때문에 틀리는 경우가 더 많습니다.

패턴 1. 정적 배열 다중 합 질의

배열이 바뀌지 않고 구간 합만 여러 번 물어본다면 누적합이 거의 항상 가장 먼저 떠올라야 한다

Princeton과 USACO Guide가 공통으로 설명하듯, 정적 배열에서 여러 구간 합 질의를 처리할 때 누적합은 전형적인 해법입니다. 전처리는 한 번만 하고, 이후 모든 질의를 즉시 계산할 수 있기 때문입니다.

:contentReference[oaicite:8]{index=8}

대표 문제 형태

• 여러 개의 [L, R] 합 질의 처리
• 특정 구간의 평균 구하기
• 좌우 부분합 비교
• 부분 배열 합 검증

:contentReference[oaicite:9]{index=9}

패턴 2. 부분 배열 합이 k인 경우 세기

구간합은 단순 질의 문제를 넘어서, prefix sum과 HashMap을 결합하면 부분 배열 합 개수 세기 문제까지 확장된다

AlgoMaster는 prefix sum + HashMap이 특정 합을 만드는 부분 배열 문제를 다루는 강력한 조합이라고 설명합니다. 핵심은 현재 누적합을 sum이라고 할 때, 이전에 sum - k가 몇 번 나왔는지를 세면 현재 위치에서 끝나는 조건 만족 구간 수를 바로 알 수 있다는 점입니다.

:contentReference[oaicite:10]{index=10}

Map<Long, Integer> count = new HashMap<>(); count.put(0L, 1);

long sum = 0;
int answer = 0;

for (int x : arr) {
sum += x;
answer += count.getOrDefault(sum - k, 0);
count.put(sum, count.getOrDefault(sum, 0) + 1);
}

이 패턴은 “합이 k인 부분 배열 개수”, “나머지가 같은 누적합 개수”, “균형 조건을 만족하는 구간 세기” 같은 문제로 자주 확장됩니다.

:contentReference[oaicite:11]{index=11}

패턴 3. 2차원 구간합

누적합은 1차원 배열에만 쓰는 기법이 아니라, 2차원 격자의 직사각형 합 질의에도 그대로 확장된다

AlgoMaster는 prefix sum이 2D grid에서도 자연스럽게 확장되며, 직사각형 합 질의를 위해 모든 (0,0)부터 (i,j)까지의 합을 전처리할 수 있다고 설명합니다. 이 경우에도 전처리는 O(mn), 질의는 O(1)이라는 기본 구조를 유지합니다.

:contentReference[oaicite:12]{index=12}

int n = board.length; int m = board[0].length; long[][] ps = new long[n + 1][m + 1];

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
ps[i][j] = board[i - 1][j - 1]
+ ps[i - 1][j]
+ ps[i][j - 1]
- ps[i - 1][j - 1];
}
}

// (r1, c1) ~ (r2, c2) 합
long rect = ps[r2 + 1][c2 + 1]
- ps[r1][c2 + 1]
- ps[r2 + 1][c1]
+ ps[r1][c1];

2차원에서는 포함-배제 원리를 함께 써야 해서, 인덱스를 n+1 × m+1로 잡는 방식이 실수를 크게 줄여 줍니다.

:contentReference[oaicite:13]{index=13}

한계와 대체 구조

구간합은 정적 배열에는 매우 강하지만, 값 갱신이 자주 생기면 누적합 하나만으로는 비효율적일 수 있다

cp-algorithms의 세그먼트 트리 설명은 단순 누적합이 구간 질의에는 강하지만, 배열 원소 하나가 바뀔 때 누적합 전체 뒤쪽을 다시 고쳐야 해서 업데이트 비용이 O(n)이 된다고 설명합니다. 즉, 질의만 많고 업데이트가 없을 때는 누적합이 좋지만, 질의와 갱신이 함께 많을 때는 세그먼트 트리나 펜윅 트리 같은 자료구조가 더 적합합니다.

:contentReference[oaicite:14]{index=14}

선택 기준

• 배열이 고정이고 질의만 많다 → 누적합
• 점 업데이트와 구간합 질의가 함께 많다 → 펜윅 트리 / 세그먼트 트리
• 구간 업데이트까지 필요하다 → 세그먼트 트리 계열을 먼저 의심

:contentReference[oaicite:15]{index=15}

자주 하는 실수

구간합 문제를 틀리는 이유는 대개 인덱스 기준 혼동, prefix[0] 처리 누락, 자료형 선택 실수, 정적 배열과 동적 배열의 구분 실패 때문이다

• 0-index와 1-index 공식을 섞어 씀
• prefix[0] = 0을 두지 않아 왼쪽 경계 예외 처리에서 실수함
• 합이 커지는데 int를 써서 오버플로우가 남
• 배열 값이 바뀌는데 누적합만 고집함
• 2차원 누적합에서 포함-배제 부호를 틀림
• 부분 배열 개수 세기에서 HashMap 초기값 0 → 1을 빼먹음

풀이 루틴

구간합 문제를 보면 먼저 배열이 변하는지, 질의가 몇 번 들어오는지, 상태가 1차원인지 2차원인지부터 정리하는 습관이 중요하다

1. 배열이 정적인지 먼저 확인한다.
2. 질의 수가 많은지 본다.
3. 구간 정보가 1차원인지 2차원인지 구분한다.
4. 누적합 배열을 n+1 또는 (n+1)×(m+1) 방식으로 만들지 결정한다.
5. 질의 공식을 먼저 쓰고, 그에 맞게 prefix 정의를 맞춘다.
6. 업데이트가 많으면 누적합 대신 다른 자료구조로 넘어갈지 판단한다.

:contentReference[oaicite:16]{index=16}

디버깅

구간합 코드가 틀릴 때는 전체 로직보다 prefix 정의와 질의 공식이 서로 정확히 맞물리는지부터 확인해야 한다

1

prefix 배열이 무엇을 뜻하는지 한 문장으로 다시 적어 본다.

2

0-index 공식인지 1-index 공식인지 하나로 통일한다.

3

prefix[0] 또는 첫 행/첫 열의 0 초기화가 빠지지 않았는지 확인한다.

4

값 범위가 크다면 자료형을 long으로 바꿔 본다.

5

업데이트가 있는 문제라면 애초에 누적합 선택이 맞았는지도 다시 본다.

요약

구간합 알고리즘의 본질은 누적합을 미리 계산해 두고 구간 질의를 차이 계산으로 바꾸는 것이며, 정적 배열 질의·부분합 패턴·2차원 직사각형 합 문제에서 특히 강력하다

• ✅ 누적합은 각 위치까지의 합을 미리 저장하는 전처리 배열이다.
• ✅ 정적 배열에서는 O(N) 전처리 후 구간 합 질의를 O(1)에 처리할 수 있다.
• ✅ prefix[0] = 0을 두는 n+1 방식이 실수를 줄이기 쉽다.
• ✅ prefix sum + HashMap은 부분 배열 합 문제를 푸는 강력한 확장 패턴이다.
• ✅ 2차원 격자에서도 직사각형 합 질의로 자연스럽게 확장된다.
• ✅ 업데이트가 많아지면 세그먼트 트리나 펜윅 트리 같은 대안 구조를 고려해야 한다.

:contentReference[oaicite:17]{index=17}

RELATED POST

메모이제이션과 누적합은 어떻게 다른가
세그먼트 트리와 펜윅 트리를 구간합 관점에서 비교하기
부분 배열 합이 k인 문제를 Prefix Sum + HashMap으로 푸는 법

::contentReference[oaicite:18]{index=18}