차분 배열

[1. 개요]

차분 배열은 배열을 효율적으로 구간 단위로 갱신 할 수 있도록 해주는 자료 구조이다.

• [a. b] 구간에 대해서 +k 를 하고,
• [c, e] 구간에 대해서 +m 을 하고,
• ...
• 이와 같은 방식으로, 구간 내 변화가 발생한다고 했을 때,
• 단순한 방법으로는 각 구간을 iterate 하면서 업데이트 하는 방법 이 있지만,
• 결국 필요한 구간 만큼 iterate 해야 하는 상황이 발생하게 된다.

즉, 쿼리 개수 (Q) 와 구간의 길이 (L) 에 대해서 시간 복잡도 O(Q * L) 이 발생하게 된다.

 

그러나 차분 배열을 이용하면 동일한 작업에 대해서 시간 복잡도를 O(Q + L) 로 낮출 수 있다.

---

[2. 차분 배열의 정의]

어떤 배열 A 가 있을 때, 차분 배열 D 는 아래와 같이 정의 된다.

• D[0] = A[0]
• D[i] = A[i] - A[i-1] , (i > 0)

즉, 차분 배열의 원소 D[i] 가 의미 하는 바는 원소 A[i] 가 이전 원소 A[i-1] 보다 얼마나 변화 했는지를 기록한다.

 

그리고, 원래 A[i] 를 구하는 방법은 차분 배열의 누적 합을 이용하여 구하게 된다.

• A[i] = D[0] + D[1] + ... + D[i]

---

[3. 구간 갱신]

배열 A 의 구간 [l, r] 에 대해서 +k 만큼 해야 한다고 할 때,

차분 배열을 이용하면 아래와 같이 진행 한다.

• D[l] += k
• D[r+1] -= k

이 연산의 의미는 아래와 같다.

• 갱신 된 A[i] 를 구할 때, 차분 배열의 누적 합을 이용하여 구하게 된다.
• 즉, D[l] += k 를 하게 되면, 갱신 된 A[i] 에는 k 가 더해지게 되고,
• D[l+1] 에도 D[l] 이 더해지기에 k 가 더해지게 된다.
• 이런식으로 D[r] 도 k 가 더해지게 된다.
• 그러나, D[r+1] 부터는 k 가 더해지면 안된다.
• 그래서 D[r+1] 에는 k 를 빼주어서 0 을 더하게 만들어 아무 영향을 끼치지 않게 하는 것이다.

---

[4. 활용]

여러 구간 업데이트를 한꺼번에 수행 한 후

마지막에 한 번만 누적합을 계산하면 전체 최종 배열을 구할 수 있다.

• 업데이트는 O(1)
• 누적 합 시 O(n) 이 발생 (n 은 배열의 길이)