Quick Comparison
| 패턴 | 먼저 하는 일 | 질의/갱신 | 대표 용도 |
|---|---|---|---|
| 누적합 | 앞에서부터 합 저장 | 구간 합 O(1) | 여러 번 구간 합 묻기 |
| 2차원 누적합 | 행과 열 방향 합 저장 | 사각형 합 O(1) | 격자 영역 합 |
| 차분 배열 | 변화량만 표시 | 구간 갱신 O(1) | 여러 구간 더하기 |
long[] prefix = BuildPrefix(values);
long sum = RangeSum(prefix, left, right); // [left, right], 양 끝 포함누적합은 만들고 나면 구간 질의를 빠르게 처리하고, 차분 배열은 갱신을 기록한 뒤 한 번에 복원합니다. 갱신과 질의가 번갈아 오면 둘만으로는 부족합니다.
누적합
누적합은 prefix[i]를 처음부터 i개 원소의 합으로 저장합니다. 이렇게 두면 [left, right] 구간 합은 오른쪽 끝까지의 합에서 왼쪽 앞까지의 합을 빼서 구합니다.
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]를 쓰는 형태가 가장 안전합니다.
static long[] BuildPrefix(IReadOnlyList<int> values)
{
var prefix = new long[values.Count + 1];
for (int i = 0; i < values.Count; i++)
{
prefix[i + 1] = prefix[i] + values[i];
}
return prefix;
}
static long RangeSum(long[] prefix, int left, int right)
{
if (left < 0 || right < left || right >= prefix.Length - 1)
{
throw new ArgumentOutOfRangeException();
}
return prefix[right + 1] - prefix[left];
}원소가 int여도 합은 int 범위를 넘기기 쉽습니다. 누적합과 결과는 먼저 long으로 두는 편이 안전합니다.
2차원 누적합
격자에서는 왼쪽, 위쪽, 대각선 중복 영역을 이용해 사각형 합을 계산합니다.
static long[,] BuildPrefix2D(int[,] grid)
{
int height = grid.GetLength(0);
int width = grid.GetLength(1);
var prefix = new long[height + 1, width + 1];
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
prefix[y + 1, x + 1] = grid[y, x]
+ prefix[y, x + 1]
+ prefix[y + 1, x]
- prefix[y, x];
}
}
return prefix;
}사각형 (y1, x1)부터 (y2, x2)까지의 합은 포함-배제 원리로 구합니다.
long[,] prefix = BuildPrefix2D(grid);
long area =
prefix[y2 + 1, x2 + 1]
- prefix[y1, x2 + 1]
- prefix[y2 + 1, x1]
+ prefix[y1, x1];차분 배열
차분 배열은 실제 값을 바로 바꾸지 않고 “여기서부터 증가”, “여기 다음부터 감소”만 기록합니다. 모든 구간 갱신을 기록한 뒤 마지막에 한 번 누적하면 최종 배열이 나옵니다.
static long[] ApplyRangeAdds(
int length,
IEnumerable<(int Left, int Right, long Value)> updates)
{
if (length < 0) throw new ArgumentOutOfRangeException(nameof(length));
var diff = new long[length + 1];
foreach (var (left, right, value) in updates)
{
if (left < 0 || right < left || right >= length)
{
throw new ArgumentOutOfRangeException();
}
diff[left] += value;
diff[right + 1] -= value; // right == length - 1이어도 diff[length]가 있어 안전
}
var added = new long[length];
long current = 0;
for (int i = 0; i < length; i++)
{
current += diff[i];
added[i] = current;
}
return added;
}위 함수는 각 위치에 더할 총량을 반환합니다. 원본 배열이 있다면 result[i] = values[i] + added[i]처럼 합쳐 사용합니다. 차분 배열을 길이 n + 1로 만들었기 때문에 마지막 원소까지 갱신해도 right + 1을 특별 처리하지 않습니다.
구간 갱신이 많고 중간 결과를 바로 묻지 않는 문제에서 효과적입니다. 각 갱신을 O(1)에 기록하고, 마지막 복원만 O(n)에 수행합니다.
선택 기준
| 문제 신호 | 선택 |
|---|---|
| 배열은 고정, 구간 합 질의가 많음 | 누적합 |
| 격자에서 사각형 합을 여러 번 물음 | 2차원 누적합 |
| 같은 배열에 여러 구간 더하기를 한 뒤 최종 결과만 필요 | 차분 배열 |
| 갱신과 질의가 섞여 온라인으로 들어옴 | Fenwick tree 또는 segment tree |
| 음수가 섞인 구간 합 조건 | 슬라이딩 윈도우보다 누적합 재검토 |
주의할 점
누적합은 index 경계가 가장 많이 틀립니다. prefix를 n + 1로 만들고, 원본 arr[i]가 prefix[i + 1]에 반영된다는 규칙을 끝까지 유지하세요. 2차원도 같은 이유로 위·왼쪽에 0으로 채운 한 줄과 한 칸을 둡니다.
차분 배열은 갱신을 모두 모은 뒤 최종 결과를 복원하는 패턴입니다. 갱신 중간에 즉시 구간 합을 계속 물어보는 문제라면 다른 자료구조가 필요합니다.
참고 링크
1 sources