[알고리즘] 40. 차분 배열(Difference Array)

[알고리즘] 40. 차분 배열(Difference Array)

지난 글에서는 구간합 문제에 대해 정리했습니다. 이번 글에서는 여러 구간에 같은 값을 더하는 문제를 효율적으로 처리하는 차분 배열(Difference Array)에 대해 알아보겠습니다.

차분 배열은 누적합과 반대 방향으로 생각하면 이해하기 쉽습니다. 누적합이 구간의 합을 빠르게 구하기 위한 기법이라면, 차분 배열은 구간에 값을 여러 번 더하는 작업을 빠르게 처리하기 위한 기법입니다.

차분 배열은 여러 구간 업데이트를 효율적으로 처리하고, 마지막에 누적합으로 실제 배열을 복원하는 기법입니다.

---

1. 차분 배열이 필요한 이유

배열의 특정 구간에 값을 더하는 문제가 있다고 하겠습니다.

배열: [0, 0, 0, 0, 0]

1번부터 3번까지 +2
2번부터 5번까지 +3

단순하게 처리하면 각 구간을 반복문으로 돌면서 값을 직접 더할 수 있습니다.

for (int i = left; i <= right; i++) {
    arr[i] += value;
}

구간 업데이트가 한두 번이면 괜찮습니다. 하지만 배열 길이 N이 크고, 구간 업데이트가 M번 주어진다면 최악의 경우 O(N × M)이 될 수 있습니다.

이런 상황에서 차분 배열을 사용하면 구간 업데이트 하나를 O(1)에 기록할 수 있습니다.

차분 배열은 구간에 값을 더하는 작업이 여러 번 나올 때 강력합니다.

---

2. 차분 배열의 핵심 아이디어

차분 배열의 핵심은 구간 전체를 직접 바꾸지 않고, 변화가 시작되는 지점과 끝나는 지점만 표시하는 것입니다.

예를 들어 2번부터 4번까지 3을 더한다고 하겠습니다.

2번부터 4번까지 +3

이때 차분 배열에는 다음처럼 기록합니다.

diff[2] += 3
diff[5] -= 3

2번부터 값이 3 증가하기 시작하고, 5번부터는 그 증가 효과가 끝난다는 의미입니다.

차분 배열은 시작점에 더하고, 끝난 다음 위치에 빼는 방식으로 구간 변화를 기록합니다.

---

3. 기본 공식

1번 인덱스 기준으로 left부터 right까지 value를 더하고 싶다면 차분 배열에는 다음처럼 기록합니다.

diff[left] += value
diff[right + 1] -= value

이 공식이 차분 배열의 핵심입니다.

작업	의미
diff[left] += value	left 위치부터 value 증가 시작
diff[right + 1] -= value	right 다음 위치부터 증가 효과 종료

마지막에는 diff 배열을 앞에서부터 누적합으로 복원하면 실제 배열의 값이 만들어집니다.

---

4. 간단한 예시

길이가 5인 배열이 있고, 처음 값은 모두 0이라고 하겠습니다.

arr:  [0, 0, 0, 0, 0]

2번부터 4번까지 3을 더하고 싶습니다.

2번부터 4번까지 +3

차분 배열에는 다음처럼 기록합니다.

diff[2] += 3
diff[5] -= 3

차분 배열은 다음과 같습니다.

인덱스: 1  2  3  4  5  6
diff:   0  3  0  0 -3  0

이제 앞에서부터 누적하면 실제 배열이 됩니다.

1번: 0
2번: 0 + 3 = 3
3번: 3 + 0 = 3
4번: 3 + 0 = 3
5번: 3 - 3 = 0

복원 결과는 다음과 같습니다.

arr: [0, 3, 3, 3, 0]

---

5. 차분 배열 Java 기본 코드

차분 배열을 이용해 하나의 구간 업데이트를 처리하는 기본 코드는 다음과 같습니다.

int n = 5;
int[] diff = new int[n + 2];

int left = 2;
int right = 4;
int value = 3;

diff[left] += value;
diff[right + 1] -= value;

int[] arr = new int[n + 1];

for (int i = 1; i <= n; i++) {
    arr[i] = arr[i - 1] + diff[i];
}

for (int i = 1; i <= n; i++) {
    System.out.print(arr[i] + " ");
}

출력 결과는 다음과 같습니다.

0 3 3 3 0

2번부터 4번까지 3이 더해진 것을 확인할 수 있습니다.

diff 배열은 n + 2 크기로 만들면 right + 1 접근을 안전하게 처리할 수 있습니다.

---

6. 여러 구간 업데이트 처리하기

차분 배열은 여러 구간 업데이트가 있을 때 진짜 힘을 발휘합니다.

길이 5 배열

1번부터 3번까지 +2
2번부터 5번까지 +3
4번부터 5번까지 -1

각 작업을 diff 배열에만 기록합니다.

1~3 +2  → diff[1] += 2, diff[4] -= 2
2~5 +3  → diff[2] += 3, diff[6] -= 3
4~5 -1  → diff[4] += -1, diff[6] -= -1

이렇게 기록한 뒤 마지막에 한 번만 누적합으로 복원하면 됩니다.

---

7. 여러 구간 업데이트 Java 코드

여러 구간 업데이트를 차분 배열로 처리하는 코드는 다음과 같습니다.

int n = 5;
int[] diff = new int[n + 2];

int[][] updates = {
    {1, 3, 2},
    {2, 5, 3},
    {4, 5, -1}
};

for (int[] update : updates) {
    int left = update[0];
    int right = update[1];
    int value = update[2];

    diff[left] += value;
    diff[right + 1] -= value;
}

int[] arr = new int[n + 1];

for (int i = 1; i <= n; i++) {
    arr[i] = arr[i - 1] + diff[i];
}

for (int i = 1; i <= n; i++) {
    System.out.print(arr[i] + " ");
}

출력 결과는 다음과 같습니다.

2 5 5 2 2

각 위치의 결과를 직접 계산해보면 다음과 같습니다.

위치	적용되는 업데이트	최종 값
1	+2	2
2	+2, +3	5
3	+2, +3	5
4	+3, -1	2
5	+3, -1	2

---

8. 직접 업데이트와 차분 배열 비교

여러 구간 업데이트를 직접 처리하면 각 업데이트마다 구간 전체를 반복해야 합니다.

for (int[] update : updates) {
    int left = update[0];
    int right = update[1];
    int value = update[2];

    for (int i = left; i <= right; i++) {
        arr[i] += value;
    }
}

이 방식은 업데이트 횟수와 구간 길이가 커질수록 느려집니다.

방식	구간 업데이트 1번	M번 업데이트	최종 복원
직접 반복문	O(N)	O(N × M)	필요 없음
차분 배열	O(1)	O(M)	O(N)

차분 배열은 업데이트를 모두 기록하는 데 O(M), 마지막에 복원하는 데 O(N)이 걸립니다. 따라서 전체 시간복잡도는 O(N + M)입니다.

차분 배열은 여러 구간 업데이트를 O(N + M)에 처리할 수 있습니다.

---

9. 기존 배열이 있는 경우

처음 배열이 모두 0이 아니라 기존 값이 있는 경우도 있습니다. 이때는 업데이트 결과를 복원한 뒤 기존 배열에 더하거나, 기존 배열의 차분 배열을 먼저 만들 수도 있습니다.

가장 단순한 방식은 업데이트용 diff를 따로 만들고, 마지막에 기존 배열에 더하는 것입니다.

int[] origin = {0, 10, 20, 30, 40, 50}; // 1번 인덱스 기준
int n = 5;

int[] diff = new int[n + 2];

diff[2] += 3;
diff[5] -= 3;

int current = 0;

for (int i = 1; i <= n; i++) {
    current += diff[i];
    origin[i] += current;
}

for (int i = 1; i <= n; i++) {
    System.out.print(origin[i] + " ");
}

위 코드는 2번부터 4번까지 3을 더합니다.

10 23 33 43 50

---

10. 기존 배열 자체를 차분 배열로 만들기

기존 배열을 기준으로 차분 배열을 만들 수도 있습니다. arr 배열이 1번 인덱스 기준이라고 하겠습니다.

arr: 10 20 30 40 50

차분 배열은 현재 값과 이전 값의 차이로 만들 수 있습니다.

diff[1] = arr[1]
diff[2] = arr[2] - arr[1]
diff[3] = arr[3] - arr[2]

Java 코드로 작성하면 다음과 같습니다.

int n = 5;
int[] arr = {0, 10, 20, 30, 40, 50};

int[] diff = new int[n + 2];

diff[1] = arr[1];

for (int i = 2; i <= n; i++) {
    diff[i] = arr[i] - arr[i - 1];
}

이렇게 만든 diff 배열에 구간 업데이트를 기록한 뒤 다시 누적합으로 복원하면 됩니다.

차분 배열은 현재 값과 이전 값의 차이를 저장하는 배열로도 이해할 수 있습니다.

---

11. 차분 배열 복원하기

차분 배열을 실제 배열로 복원하려면 앞에서부터 누적합을 구하면 됩니다.

arr[i] = arr[i - 1] + diff[i]

예를 들어 diff 배열이 다음과 같다고 하겠습니다.

diff: 10 10 10 10 10

누적하면 실제 배열은 다음과 같습니다.

arr[1] = 10
arr[2] = 20
arr[3] = 30
arr[4] = 40
arr[5] = 50

즉 차분 배열은 누적합을 통해 실제 배열로 되돌릴 수 있습니다.

---

12. 음수 업데이트도 가능할까요?

차분 배열은 값을 더하는 작업뿐 아니라 빼는 작업도 처리할 수 있습니다. value가 음수이면 구간 전체에서 값을 빼는 효과가 납니다.

2번부터 4번까지 -3

이 경우에도 공식은 같습니다.

diff[2] += -3
diff[5] -= -3

diff[5] -= -3은 diff[5]에 3을 더하는 것과 같습니다. 즉 5번부터는 감소 효과가 끝나야 하므로 다시 +3이 되는 것입니다.

차분 배열은 양수 업데이트와 음수 업데이트를 모두 처리할 수 있습니다.

---

13. long을 사용해야 하는 경우

구간 업데이트 값이 크거나 업데이트 횟수가 많으면 최종 값이 int 범위를 넘을 수 있습니다. 이런 경우 diff 배열과 결과 배열을 long으로 만드는 것이 안전합니다.

업데이트 값: 1,000,000
업데이트 횟수: 100,000

한 위치에 누적될 수 있는 값: 100,000,000,000

이 값은 int 범위를 넘습니다. 따라서 다음처럼 long[]을 사용할 수 있습니다.

long[] diff = new long[n + 2];
long[] arr = new long[n + 1];

차분 배열도 누적 결과가 커질 수 있으므로 long 사용 여부를 확인해야 합니다.

---

14. 2차원 차분 배열 맛보기

차분 배열은 2차원 배열에서도 사용할 수 있습니다. 2차원 차분 배열은 특정 직사각형 영역에 같은 값을 더하는 문제에서 사용합니다.

표에서 (x1, y1)부터 (x2, y2)까지 +value

2차원에서는 네 꼭짓점에 값을 표시하는 방식으로 처리합니다.

diff[x1][y1] += value
diff[x2 + 1][y1] -= value
diff[x1][y2 + 1] -= value
diff[x2 + 1][y2 + 1] += value

이후 행과 열 방향으로 누적합을 적용하면 실제 2차원 배열을 복원할 수 있습니다. 2차원 차분 배열은 조금 더 복잡하므로 여기서는 개념만 잡고 넘어가겠습니다.

2차원 차분 배열은 직사각형 영역 업데이트를 빠르게 처리할 때 사용합니다.

---

15. 차분 배열이 사용되는 대표 문제

차분 배열은 아래와 같은 문제에서 자주 사용됩니다.

문제 유형	설명
여러 구간에 값 더하기	left부터 right까지 value를 여러 번 더함
구간 변화량 처리	특정 구간에서 증가나 감소가 반복됨
좌석 예약 / 인원 변화	특정 구간에 인원이 추가되거나 빠짐
공사 구간 / 영향 범위	여러 구간에 영향이 누적됨
2차원 영역 업데이트	직사각형 영역에 값을 더함

문제를 보고 “여러 구간에 같은 값을 더한다”, “업데이트가 많다”, “마지막 결과만 필요하다”는 느낌이 들면 차분 배열을 고려해볼 수 있습니다.

---

16. 차분 배열에서 자주 하는 실수

차분 배열 문제를 풀 때는 아래 실수를 조심해야 합니다.

• diff 배열 크기를 n + 2로 만들지 않아 right + 1에서 오류가 나는 경우
• diff[left]에는 더하고 diff[right + 1]에는 빼는 공식을 반대로 쓰는 경우
• right + 1 위치에 빼는 작업을 빠뜨리는 경우
• 업데이트를 기록한 뒤 누적합으로 복원하지 않는 경우
• 0번 인덱스 기준과 1번 인덱스 기준을 섞어서 사용하는 경우
• 기존 배열이 있는데 업데이트 결과만 출력하는 경우
• 값이 커질 수 있는데 int 배열을 사용하는 경우

특히 아래 공식은 반드시 기억해야 합니다.

left부터 right까지 value 더하기:
diff[left] += value
diff[right + 1] -= value

차분 배열 실수는 대부분 right + 1 처리와 마지막 복원 과정에서 발생합니다.

---

17. 정리

이번 글에서는 차분 배열에 대해 정리했습니다.

• 차분 배열은 여러 구간 업데이트를 빠르게 처리하는 기법이다.
• 구간 전체를 직접 바꾸지 않고 시작점과 끝 다음 지점만 표시한다.
• left부터 right까지 value를 더할 때 diff[left] += value, diff[right + 1] -= value를 사용한다.
• 모든 업데이트를 기록한 뒤 누적합으로 실제 배열을 복원한다.
• 구간 업데이트 하나를 O(1)에 기록할 수 있다.
• M번 업데이트 후 전체 복원까지 O(N + M)에 처리할 수 있다.
• 기존 배열이 있는 경우 기존 값과 업데이트 누적 결과를 함께 고려해야 한다.
• 값이 커질 수 있다면 long[]을 사용하는 것이 안전하다.

차분 배열은 누적합과 함께 구간 처리 문제에서 매우 중요한 기법입니다. 누적합이 구간 합을 빠르게 구하는 도구라면, 차분 배열은 구간 업데이트를 빠르게 기록하는 도구입니다.

차분 배열의 핵심은 구간의 시작과 끝 다음 지점에 변화량만 기록하고, 마지막에 누적합으로 실제 값을 복원하는 것입니다.

---

다음 글 예고

다음 글에서는 그리디 알고리즘 기초에 대해 알아보겠습니다.

매 순간 가장 좋아 보이는 선택을 하는 그리디의 개념, 정렬과의 관계, 그리디가 통하는 조건과 자주 나오는 문제 패턴을 예제로 정리해보겠습니다.