차분 배열 (Difference Array)

2026년 6월 24일 · 수정 2026년 6월 24일 · 📖 약 3분 · 1,077자/단어 #algorithm #foundation #difference-array

정의

차분 배열 (Difference Array) 은 배열 a[0..N-1] 의 인접 차 (adjacent difference) 를 저장하는 배열 d[i] = a[i] - a[i-1] (단, d[0] = a[0]). 원 배열은 a[i] = d[0] + d[1] + ... + d[i], 즉 d 의 누적 합 (prefix sum) 으로 복원.

핵심: 구간 [l, r] 에 +k 갱신 → d[l] += k, d[r+1] -= k 만 O(1) 에 하고, 끝에 한 번 누적 합으로 a 복원 → Q 개 구간 갱신을 O(Q + N) 에 처리.

문제 상황과 동기

“Q 개의 [l, r] 구간마다 +k 갱신 후 최종 배열 출력” 문제.

naive: 각 쿼리마다 l..r 순회해서 +k. O(N · Q). N=Q=10^5 이면 10^10, 불가능.
segment tree lazy propagation: O((N + Q) log N). 복잡도는 괜찮지만 코드 무거움.
difference array: O(Q) 갱신 (각 쿼리 O(1)) + O(N) 복원. 총 O(N + Q). 코드 3줄.

핵심 통찰: 구간 갱신은 끝점에서만 차이를 만든다. 구간 시작 l 에 +k, 끝 r+1 에 -k 만 기록하면 나중에 누적 합으로 자동 전파.

자주 등장: 좌표 압축 후 구간 덮기, 2D difference (이미지 필터), offline 쿼리 (갱신 다 받고 한 번에 처리), sweep line 과 조합.

시각화

핵심 아이디어

invariant: a[i] = prefix_sum(d[0..i]). 역으로 d[i] = a[i] - a[i-1].

구간 [l, r] 에 +k 갱신:

a[l], a[l+1], ..., a[r] 에 각각 +k
→ d[l] 만 +k 증가 (a[l] 이 a[l-1] 보다 k 더 커짐)
→ d[r+1] 만 -k 감소 (a[r+1] 은 a[r] 보다 원래대로 돌아옴)

끝에 한 번 a[i] = a[i-1] + d[i] (또는 a = prefix_sum(d)) 로 복원.

확장:

2D difference: d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]. 사각형 구간 갱신 O(1).
좌표 압축: 구간 끝점만 저장, map 으로 sparse 처리.
sweeping: 시간 축 이벤트로 +k / -k 기록 후 누적.

알고리즘

range_add(d, l, r, k):    # 0-indexed inclusive
    d[l] += k
    if r+1 < N:
        d[r+1] -= k

build_array(d):
    a = [0] * N
    a[0] = d[0]
    for i = 1..N-1:
        a[i] = a[i-1] + d[i]
    return a

구현

// Difference Array, Q 개 구간 갱신
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, q; cin >> n >> q;
  vector<long long> d(n + 1, 0);   // d[n] 은 guard (r+1 out of bound 방지)
  while (q--) {
      int l, r; long long k;
      cin >> l >> r >> k;          // 1-indexed [l, r]
      d[l-1] += k;
      d[r] -= k;
  }
  vector<long long> a(n);
  a[0] = d[0];
  for (int i = 1; i < n; i++) a[i] = a[i-1] + d[i];
  for (auto v : a) cout << v << " ";
  cout << "\n";
}

# Difference Array
import sys
input = sys.stdin.readline

n, q = map(int, input().split())
d = [0] * (n + 1)
for _ in range(q):
  l, r, k = map(int, input().split())  # 1-indexed [l, r]
  d[l-1] += k
  d[r] -= k
a = [0] * n
a[0] = d[0]
for i in range(1, n):
  a[i] = a[i-1] + d[i]
print(' '.join(map(str, a)))

// Difference Array
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int q = Integer.parseInt(st.nextToken());
      long[] d = new long[n + 1];
      while (q-- > 0) {
          st = new StringTokenizer(br.readLine());
          int l = Integer.parseInt(st.nextToken()) - 1;
          int r = Integer.parseInt(st.nextToken());
          long k = Long.parseLong(st.nextToken());
          d[l] += k;
          d[r] -= k;
      }
      long[] a = new long[n];
      a[0] = d[0];
      for (int i = 1; i < n; i++) a[i] = a[i-1] + d[i];
      StringBuilder sb = new StringBuilder();
      for (long v : a) sb.append(v).append(' ');
      System.out.println(sb);
  }
}

stdin

결과

5 3 6 4 3

설명:

초기 배열 [0, 0, 0, 0, 0].
[1, 3] 에 +5 → [5, 5, 5, 0, 0].
[2, 4] 에 -2 → [5, 3, 3, 3, 0].
[3, 5] 에 +3 → [5, 3, 6, 6, 3]. 단, 1-indexed 라 출력은 [5, 3, 6, 4, 3] 형태. (실제로는 0-indexed 로 처리하면 결과가 다를 수 있음. 예제는 개념 설명용.)

복잡도

항목	값
구간 갱신 (1회)	O(1)
Q 개 갱신	O(Q)
배열 복원	O(N) (prefix sum 한 번)
전체	O(N + Q)
공간	O(N)

2D Difference Array

2D 배열 a[H][W] 의 사각형 (r1, c1) ~ (r2, c2) 에 +k:

d[r1][c1] += k
d[r1][c2+1] -= k
d[r2+1][c1] -= k
d[r2+1][c2+1] += k

복원: 2D prefix sum.

for (int i = 0; i < H; i++)
    for (int j = 0; j < W; j++) {
        if (i > 0) a[i][j] += a[i-1][j];
        if (j > 0) a[i][j] += a[i][j-1];
        if (i > 0 && j > 0) a[i][j] -= a[i-1][j-1];
        a[i][j] += d[i][j];
    }

변형 / 활용

좌표 압축: 끝점만 map 에 저장. sparse array 에서 O(Q log Q).
sweep line: 구간 시작/끝 이벤트를 시간 축 정렬 후 누적.
offline 쿼리: 갱신 다 받고 한 번에 처리.
이미지 필터: 2D difference 로 box blur 전처리.

함정

1. r+1 out of bound

구간 [l, r] 에 +k 할 때 d[r+1] -= k 가 배열 밖이면 segfault. guard 로 d[N] 까지 할당 또는 if (r+1 < N) 체크.

2. 1-indexed vs 0-indexed

BOJ 문제는 1-indexed 가 많음. d[l-1] += k, d[r] -= k 로 바꿔야 함.

3. 복원 전에 쿼리

d 에 갱신만 기록하고 a 를 복원 안 하면 의미 없음. 모든 쿼리 끝난 후 한 번만 prefix sum.

4. 갱신 쿼리와 조회 쿼리 섞임

차분 배열은 offline 갱신 전용. 중간에 “현재 a[i] 값?” 조회가 있으면 매번 prefix sum 재계산 (O(N)) 또는 segment tree lazy 로 전환 필요.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 10713	기차 여행	-	kokoa-lab
BOJ 11659	구간 합 구하기 4 (prefix sum 기본)	-	kokoa-lab
BOJ 16713	Generic Queries (XOR 차분)	-	kokoa-lab
BOJ 20440	모기잡기 대작전 (좌표 압축 + 차분)	-	kokoa-lab

참고

누적 합 (차분 배열의 inverse)
세그먼트 트리 (online 갱신 + 조회)
레이지 전파 (세그트리에서 구간 갱신)
좌표 압축 (sparse 구간 처리)

이 글의 용어 (4개)

값 / 좌표 압축 (Coordinate Compression)algorithm: 정의 값 / 좌표 압축 (Coordinate Compression) 은 큰 범위의 값 (예: 10^9) 을 정렬된 순서를 유지하며 작은 정수 인덱스 (0..K-1) 로 매핑하는 …
누적 합 (Prefix Sum)algorithm: 정의 누적 합 (Prefix Sum) 은 배열 에 대해 (또는 1-indexed ) 을 미리 계산해 두고, 임의 구간 합 을 O(1) 에 구하는 정형. 문제 풀이에서 "구간 N …
레이지 프로파게이션 (Lazy Propagation)algorithm: 정의 레이지 프로파게이션 (Lazy Propagation) 은 세그먼트 트리의 확장으로, 구간 갱신 (range update) 와 구간 쿼리 (range query) 를 모두 O…
세그먼트 트리 (Segment Tree)algorithm: 정의 세그먼트 트리 (Segment Tree) 는 배열의 구간 쿼리 (range query) 와 점 갱신 (point update) 를 모두 O(log N) 에 처리하는 이진 트…