차분 배열

차분배열 Difference Array

구간 업데이트를 빠르게 수행하기 위한 기법입니다.
일반적으로는 특정 구간 업데이트는 O(n) 만큼 걸리지만 차분 배열을 사용하면 O(1)에 가능하다.

누적합을 문제를 풀 때 이러한 방법을 쓴 적이 있지만 특정 기법이 있는지는 잘 몰랐어서 정리를 해보려고 한다.

기본 개념

직관적으로 사용할 때는

A = [1, 2, 3, 4, 5]  

라는 배열이 존재하고
0번 인덱스 ~ 2번 인덱스까지 2씩 더할려고 하면

A[0] += 2  
A[1] += 2  
A[2] += 2  

이런 방식으로 총 3번에 걸쳐서 수행이 된다.
이러한 방식으로 여러 번 반복을 할 경우 시간 복잡도가 많이 올라가게 된다.

차분배열을 사용해보자

차분배열을 사용하려면 "배열의 크기 + 1" 크기에 해당하는 배열을 하나 만들어준다.

arr = [0, 0, 0, 0, 0, 0]

여기서 똑같이
0번 인덱스 ~ 2번 인덱스까지 2씩 더해보자
그러면

arr[0] += 2 // 시작 인덱스, 0
arr[3] -= 2 // 종료 인덱스 + 1, 2 + 1

이렇게 구간을 저장해준다.
그리고 실제 값을 더해줄 때는

curValue = 0
for i in range(5):
    curValue += arr[i]
    A[i] += curValue

처음부터 끝까지 인덱스를 돌게 된다면 O(N) 으로 구간 업데이트가 된 실제 배열로 복원을 할 수 있게 된다.

동작과정을 보면 아래와 같이 동작을 하게 된다.

0 번 인덱스 -> arr[0] = 2 이므로 curValue = 2, 2를 더해준다
1번 인덱스 -> arr[1] = 0, curValue = 2, 2를 더해준다
2번 인덱스 -> arr[2] = 0, curValue = 2, 2를 더해준다
3번 인덱스 -> arr[3] = -2, curValue = 2 - 2 , 0 을 더해준다.
4번 인덱스 -> arr[4] = 0, curValue = 0, 0을 더해준다.

한번 업데이트에서 효율적으로 동작한다보다는 업데이트가 여러 번 반복되는 상황에서 효율적으로 계산을 할 수 있게 된다.