누적합과 차분 배열: 구간 합과 구간 업데이트를 한 흐름으로 이해하기

누적합과 차분 배열은 따로 외우면 자꾸 헷갈리지만, 역할로 나누면 생각보다 단순합니다. 누적합은 구간 합을 빨리 읽는 도구이고, 차분 배열은 구간 업데이트를 빨리 기록하는 도구입니다.

코딩테스트에서 시간 초과가 나는 순간도 대개 여기서 갈립니다. 질문이 많으면 누적합을 보고, 업데이트가 많으면 차분 배열을 보고, 둘 다 자주 섞이면 다른 자료구조까지 생각해야 합니다.

문제 신호

문제를 읽을 때 먼저 봐야 하는 것은 배열이 아니라 질문의 종류입니다. 배열은 거의 고정되어 있고 l부터 r까지 합을 여러 번 구하라는 문제라면 누적합 쪽이고, l부터 r까지 같은 값을 여러 번 더하라는 문제라면 차분 배열 쪽입니다.

둘 다 구간을 다루지만 자주 하는 일이 다릅니다. 그래서 같은 배열 문제처럼 보여도 도구 선택은 완전히 달라질 수 있습니다.

누적합 핵심

누적합은 앞에서부터의 합을 미리 저장합니다. 배열이 [2, 1, 3, 4, 5]라면 prefix[i]는 앞에서부터 i개 원소의 합을 의미하게 만들 수 있습니다.

그러면 구간 합은 prefix[r + 1] - prefix[l]처럼 바로 계산할 수 있습니다. 핵심은 여러 번 읽을 구간 합을, 한 번 미리 계산해 둔다는 점입니다.

arr = [2, 1, 3, 4, 5]
prefix = [0] * (len(arr) + 1)

for i in range(len(arr)):
    prefix[i + 1] = prefix[i] + arr[i]

# 1번 인덱스부터 3번 인덱스까지 합: 1 + 3 + 4 = 8
l, r = 1, 3
range_sum = prefix[r + 1] - prefix[l]
print(range_sum)

arr = [2, 1, 3, 4, 5]
prefix = [0] * (len(arr) + 1)

for i in range(len(arr)):
    prefix[i + 1] = prefix[i] + arr[i]

# 1번 인덱스부터 3번 인덱스까지 합: 1 + 3 + 4 = 8
l, r = 1, 3
range_sum = prefix[r + 1] - prefix[l]
print(range_sum)

USACO Guide의 Introduction to Prefix Sums도 이 흐름을 정적 배열의 대표 패턴으로 설명합니다. 초기 계산은 O(N)이고, 이후 각 구간 합 질의는 O(1)이라서 전체는 보통 O(N + Q)로 정리됩니다.

누적합 한계

문제는 업데이트가 많아질 때입니다. 예를 들어 [l, r] 구간에 x를 더하는 작업이 자주 들어오면, 매번 실제 배열을 전부 바꾸는 순간 O(NM) 쪽으로 무너지기 쉽습니다.

배열이 바뀌면 누적합도 다시 맞춰야 하므로, 누적합은 읽기에는 빠르지만 쓰기에는 약한 정적 도구에 가깝습니다. 여기서 차분 배열이 등장합니다.

차분 배열 핵심

차분 배열은 값 자체보다 변화가 시작되는 지점과 끝나는 지점을 기록합니다. 배열 arr가 있을 때 보통 diff[0] = arr[0], diff[i] = arr[i] - arr[i - 1]처럼 생각할 수 있습니다.

WCIPEG의 Prefix sum array and difference array도 difference array와 prefix sum array를 서로 반대 방향의 과정으로 설명합니다. 차분 배열은 실제 값 배열이 아니라 변화량을 기록한 배열이라는 감각이 중요합니다.

그래서 구간 [l, r]에 x를 더할 때 실제 원소를 전부 바꾸지 않고, diff[l] += x와 diff[r + 1] -= x만 기록하면 됩니다.

r+1 규칙

l에서 +x를 넣으면 누적합으로 복원할 때 l부터 뒤쪽 값들이 모두 x의 영향을 받습니다. 그런데 우리는 r까지만 영향을 줘야 합니다.

그래서 r + 1에서 -x를 넣어 그 효과를 끊습니다. 그러면 누적 과정에서 l부터 r까지는 x가 살아 있고, r + 1부터는 다시 사라집니다.

차분 배열에서 l에 더하고 r+1에서 빼는 이유는, 누적될 효과의 시작점과 종료점을 표시하기 위해서입니다.

차분 배열 예시

길이 5짜리 0 배열이 있다고 해보겠습니다. 여기에 [1, 3] 구간에 2 더하기, [2, 4] 구간에 3 더하기를 차례로 적용한다고 하겠습니다.

원소를 직접 바꾸면 매번 구간 길이만큼 손이 가지만, 차분 배열은 각 업데이트마다 두 군데만 기록합니다. 그리고 마지막에 한 번만 누적해서 실제 배열을 복원합니다.

n = 5
diff = [0] * (n + 1)

updates = [
    (1, 3, 2),
    (2, 4, 3),
]

for l, r, x in updates:
    diff[l] += x
    if r + 1 < len(diff):
        diff[r + 1] -= x

arr = [0] * n
running = 0
for i in range(n):
    running += diff[i]
    arr[i] = running

print(arr)  # [0, 2, 5, 5, 3]

n = 5
diff = [0] * (n + 1)

updates = [
    (1, 3, 2),
    (2, 4, 3),
]

for l, r, x in updates:
    diff[l] += x
    if r + 1 < len(diff):
        diff[r + 1] -= x

arr = [0] * n
running = 0
for i in range(n):
    running += diff[i]
    arr[i] = running

print(arr)  # [0, 2, 5, 5, 3]

USACO Guide의 More on Prefix Sums에 나오는 Difference Arrays 설명도 비슷한 흐름입니다. 구간마다 전부 더하지 않고, 시작점과 끝 다음 지점만 바꾼 뒤 prefix sum으로 실제 적용 결과를 복원합니다.

여기서 중요한 점은 하나 더 있습니다. 차분 배열은 업데이트를 빠르게 기록할 뿐이고, 실제 배열을 얻으려면 마지막에 다시 누적합을 해야 합니다. 즉 차분 배열과 누적합은 경쟁 관계가 아니라 연결 관계입니다.

누적합과 차분 배열 선택

• 배열이 고정이고 구간 합 질의가 많다 → 누적합
• 구간 업데이트가 많고 마지막 배열이 필요하다 → 차분 배열
• 업데이트와 질의가 중간중간 계속 섞인다 → 누적합이나 차분 배열만으로는 부족할 수 있음

이 구분이 중요한 이유는 구간이라는 공통 단어보다 무엇을 자주 하느냐가 더 중요하기 때문입니다. 애드혹 문제에서 빠르게 판단할 때도 이 질문이 훨씬 잘 통합니다.

코드 비교

느린 접근은 보통 모든 업데이트마다 실제 구간을 직접 순회합니다. 업데이트 수가 많고 구간이 길수록 바로 비효율적이 됩니다.

for l, r, x in updates:
    for i in range(l, r + 1):
        arr[i] += x

for l, r, x in updates:
    for i in range(l, r + 1):
        arr[i] += x

차분 배열 접근은 매 업데이트마다 딱 두 군데만 만지고, 마지막에 한 번 누적합니다. 읽기 비용을 미리 땡겨 오는 것이 누적합이라면, 쓰기 비용을 뒤로 미루는 것이 차분 배열이라고 볼 수 있습니다.

for l, r, x in updates:
    diff[l] += x
    if r + 1 < len(diff):
        diff[r + 1] -= x

running = 0
for i in range(n):
    running += diff[i]
    arr[i] = running

for l, r, x in updates:
    diff[l] += x
    if r + 1 < len(diff):
        diff[r + 1] -= x

running = 0
for i in range(n):
    running += diff[i]
    arr[i] = running

애드혹 판단

애드혹 문제에서는 공식 이름보다 신호를 먼저 보는 편이 낫습니다. 배열은 거의 안 바뀌는지, 구간 합을 여러 번 묻는지, 구간 전체에 같은 값을 여러 번 더하는지, 최종 배열만 필요하고 중간 합 질의는 없는지를 먼저 체크해 보면 됩니다.

문제를 읽자마자 구간이라는 단어 하나만 보고 누적합부터 떠올리면 자주 틀립니다. 구간에서 무엇을 자주 하느냐를 먼저 보면 누적합과 차분 배열의 경계가 훨씬 선명해집니다.

둘 다 부족한 때

중간중간 업데이트도 자주 들어오고 그 사이사이에 구간 합 질의도 자주 들어오면 이야기가 달라집니다. 이때는 누적합은 업데이트가 느리고, 차분 배열은 중간 질의가 불편합니다.

이 구간부터는 Fenwick Tree나 Segment Tree 같은 동적 자료구조를 봐야 할 수 있습니다. cp-algorithms의 Fenwick Tree 설명도 구간 합과 업데이트를 O(log N)에 다루는 대표 구조로 이 지점을 잘 보여줍니다.

2차원 확장

이 감각은 2차원에서도 그대로 이어집니다. 2차원 누적합은 부분 직사각형 합을 빠르게 읽는 도구이고, 2차원 차분 배열은 직사각형 업데이트를 빠르게 기록하는 도구입니다.

이번 글의 핵심은 1차원에 있지만, 격자 문제를 만나도 같은 사고를 옮기면 됩니다. 읽기가 많은지, 쓰기가 많은지부터 보면 됩니다.

정리

누적합은 구간 합을 빨리 읽는 도구입니다. 차분 배열은 구간 업데이트를 빨리 기록하는 도구입니다. 그리고 차분 배열을 마지막에 누적합하면 실제 배열이 복원됩니다.

그래서 둘은 따로 외울 개념이 아니라, 구간 문제를 읽고 읽기 중심인지 쓰기 중심인지 판별하는 한 쌍의 도구로 이해하는 편이 훨씬 좋습니다.

관련 글로는 애드혹 문제란 무엇인가, 애드혹 문제 풀이법: 규칙 찾기와 반례, 좌표 압축은 언제 필요할까를 함께 보면 흐름이 더 잘 이어집니다.