빠른 비교
| 패턴 | 먼저 하는 일 | 질의/갱신 | 대표 용도 |
|---|---|---|---|
| 누적합 | 앞에서부터 합 저장 | 구간 합 O(1) | 여러 번 구간 합 묻기 |
| 2차원 누적합 | 행과 열 방향 합 저장 | 사각형 합 O(1) | 격자 영역 합 |
| 차분 배열 | 변화량만 표시 | 구간 갱신 O(1) | 여러 구간 더하기 |
csharp
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++)
{
prefix[i + 1] = prefix[i] + arr[i];
}
int sum = prefix[right + 1] - prefix[left];누적합
누적합은 prefix[i]를 처음부터 i개 원소의 합으로 저장합니다. 이렇게 두면 [left, right] 구간 합은 오른쪽 끝까지의 합에서 왼쪽 앞까지의 합을 빼서 구합니다.
text
arr: 3 1 4 1 5
prefix: 0 3 4 8 9 14
sum(1..3) = prefix[4] - prefix[1] = 9 - 3 = 6prefix를 길이 n + 1로 두면 left == 0인 경우도 같은 식으로 처리할 수 있습니다. 별도 if 없이 prefix[right + 1] - prefix[left]를 쓰는 형태가 가장 안전합니다.
2차원 누적합
격자에서는 왼쪽, 위쪽, 대각선 중복 영역을 이용해 사각형 합을 계산합니다.
csharp
sum[y + 1, x + 1] =
grid[y, x]
+ sum[y, x + 1]
+ sum[y + 1, x]
- sum[y, x];사각형 (y1, x1)부터 (y2, x2)까지의 합은 포함-배제 원리로 구합니다.
csharp
int area =
sum[y2 + 1, x2 + 1]
- sum[y1, x2 + 1]
- sum[y2 + 1, x1]
+ sum[y1, x1];차분 배열
차분 배열은 실제 값을 바로 바꾸지 않고 “여기서부터 증가”, “여기 다음부터 감소”만 기록합니다. 모든 구간 갱신을 기록한 뒤 마지막에 한 번 누적하면 최종 배열이 나옵니다.
csharp
int[] diff = new int[n + 1];
// [left, right]에 value 더하기
diff[left] += value;
diff[right + 1] -= value;
int current = 0;
for (int i = 0; i < n; i++)
{
current += diff[i];
arr[i] += current;
}구간 갱신이 많고 중간 결과를 바로 묻지 않는 문제에서 효과적입니다. 각 갱신을 O(1)에 기록하고, 마지막 복원만 O(n)에 수행합니다.
선택 기준
| 문제 신호 | 선택 |
|---|---|
| 배열은 고정, 구간 합 질의가 많음 | 누적합 |
| 격자에서 사각형 합을 여러 번 물음 | 2차원 누적합 |
| 같은 배열에 여러 구간 더하기를 한 뒤 최종 결과만 필요 | 차분 배열 |
| 갱신과 질의가 섞여 온라인으로 들어옴 | Fenwick tree 또는 segment tree |
| 음수가 섞인 구간 합 조건 | 슬라이딩 윈도우보다 누적합 재검토 |
주의할 점
누적합은 index 경계가 가장 많이 틀립니다. prefix를 n + 1로 만들고, 원본 arr[i]가 prefix[i + 1]에 반영된다는 규칙을 끝까지 유지하세요.
차분 배열은 갱신을 모두 모은 뒤 최종 결과를 복원하는 패턴입니다. 갱신 중간에 즉시 구간 합을 계속 물어보는 문제라면 다른 자료구조가 필요합니다.