차분 배열 (Difference Array)

배열의 특정 범위에 값을 더하거나 빼는 연산을 아주 효율적으로 처리하기 위한 알고리즘 기법

https://www.acmicpc.net/problem/19951
위 문제를 풀면서 차분 배열이라는 개념을 처음 알게되었다.

문제에서 길이가 100,000이고 100,000명의 조교가 연병장의 크기만큼 흙을 덮는 경우 시간복잡도가 커져 시간 초과가 발생한다.

동작 원리

차분 배열 difArr는 연산이 수행되어야하는 시작 인덱스와 끝 인덱스에만 연산 값을 적용한다.

이를 통해, 긴 길이에 적용해야 하는 연산도 O(1)의 속도로 수행할 수 있게 된다.

// i인덱스부터 j인덱스까지 +n 연산을 해야할 때

difArr[i] += n;
difArr[j + 1] -= n; 

위와 같은 방식으로 만들어진 차분 배열로 누적합을 구하면, 연산들의 최종 결과를 반영한 배열이 완성된다

예시

길이가 5인 배열 [0, 0, 0, 0, 0]이 존재한다고 가정한다.

다음 연산들을 수행하여 차분 배열을 완성한다.

1. 1~3 인덱스에 +5 연산

2. 2~4 인덱스에 -8 연산

3. 0~2 인덱스에 +3 연산

과정

1. 1~3 인덱스에 +5 연산

difArr[1] += 5;
difArr[3 + 1] -= 5;

갱신된 배열: [0, 5, 0, 0, -5]

2. 2~4 인덱스에 -8 연산

difArr[2] += (-8);
difArr[4 + 1] -= (-8); // 이 경우는 인덱스를 넘어가므로 무시

갱신된 배열: [0, 5, -8, 0, -5]

3. 0~2 인덱스에 +3 연산

difArr[0] += 3;
difArr[2 + 1] -= 3;

갱신된 배열: [3, 5, -8, -3, -5]

완성된 차분 배열로 누적합을 구하면 모든 연산이 완료된 배열을 얻을 수 있다.

누적합 배열: [3, 8, 0, -3, -8]

결론적으로 차분 배열 기법은 길이가 n, 연산 횟수가 m인 경우에 O(n + 2m)의 효율적인 시간복잡도를 가진다.