차이 배열 (Difference Array)

지난 글에서 구간 합을 O(1)에 조회하는 누적 합을 다뤘습니다. 이번에는 그 역방향 — 구간 일괄 업데이트를 O(1)에 처리하는 차이 배열(Difference Array)입니다.

핵심 아이디어

차이 배열 D[i] = A[i] - A[i-1]을 정의합니다. (D[0] = A[0])

A[l..r] += v를 수행하면:

• D[l] += v (구간 시작: v만큼 증가)
• D[r+1] -= v (구간 끝+1: v만큼 감소)

두 점만 수정하므로 O(1). 모든 업데이트 완료 후 D의 누적 합으로 O(N)에 최종 A를 복원합니다.

왜 동작하는가

A[l..r] += v 효과를 D에서 보면:

• 인덱스 l부터 r까지 D의 누적 합에 v가 더해집니다.
• 인덱스 r+1부터 D[r+1] -= v로 v가 상쇄됩니다.

D의 누적 합 = 누적 합(D) = 원본 배열 A. 차이 배열은 누적 합의 역연산입니다.

구현

def range_update(n, operations):
    """operations: [(l, r, v), ...]  A[l..r] += v"""
    D = [0] * (n + 1)
    for l, r, v in operations:
        D[l] += v
        if r + 1 <= n:
            D[r + 1] -= v
    # 누적 합으로 복원
    for i in range(1, n):
        D[i] += D[i - 1]
    return D[:n]

응용 1: 항공편 예약

bookings[i] = [first, last, seats]: 항공편 [first, last] 구간에 seats석 예약.

def corp_flight_bookings(bookings, n):
    D = [0] * (n + 1)
    for l, r, v in bookings:
        D[l - 1] += v       # 1-indexed → 0-indexed
        if r < n:
            D[r] -= v
    for i in range(1, n):
        D[i] += D[i - 1]
    return D[:n]

# 예: bookings = [[1,2,10],[2,3,20],[2,5,25]], n=5
# 결과: [10, 55, 45, 25, 25]

Q개 예약 처리: O(Q + N). 순수 루프 O(NQ) 대비 극적으로 빠릅니다.

응용 2: 최대 동시 이벤트 수

def max_concurrent(intervals):
    """intervals: [(start, end), ...]"""
    if not intervals:
        return 0
    max_t = max(e for _, e in intervals)
    D = [0] * (max_t + 2)
    for s, e in intervals:
        D[s] += 1
        D[e + 1] -= 1
    # 누적 합의 최댓값
    cur = 0
    return max((cur := cur + d) for d in D)

응용 3: 2차원 차이 배열

행렬에서 직사각형 구간 일괄 업데이트를 O(1)에 처리합니다.

def build_2d_diff(R, C):
    return [[0] * (C + 2) for _ in range(R + 2)]

def update_2d(D, r1, c1, r2, c2, v):
    D[r1][c1] += v
    D[r1][c2 + 1] -= v
    D[r2 + 1][c1] -= v
    D[r2 + 1][c2 + 1] += v  # 포함·배제 보정

def restore_2d(D, R, C):
    A = [[0] * C for _ in range(R)]
    for r in range(R):
        for c in range(C):
            val = D[r][c]
            if r > 0: val += A[r-1][c]
            if c > 0: val += A[r][c-1]
            if r > 0 and c > 0: val -= A[r-1][c-1]
            A[r][c] = val
    return A

차이 배열 vs 세그먼트 트리

항목	차이 배열	세그먼트 트리
구간 업데이트	O(1)	O(log N)
중간 조회	불가 (복원 전)	O(log N)
최종 복원	O(N)	—
구현 복잡도	매우 단순	복잡

업데이트를 모두 적용한 후 한 번에 전체 배열을 봐야 한다면 차이 배열이 최적입니다. 업데이트 중간에 조회가 필요하면 세그먼트 트리 또는 펜윅 트리를 써야 합니다.

---

지난 글: 누적 합(Prefix Sum)

다음 글: 카데인 알고리즘(Kadane’s Algorithm)

읽어주셔서 감사합니다. 😊