PrefixSum +1-1 기법 또는 차분 배열 기법(Difference Array Technique)

Difference Array Technique

이 기법은 주로 누적 합(Prefix Sum)과 함께 사용되며, 배열의 연속적인 부분에 대한 업데이트를 빠르게 수행할 수 있도록 해준다.

• 효율적인 업데이트: 배열의 큰 구간을 한 번의 연산으로 업데이트할 수 있다. 이는 구간에 포함된 각 요소를 개별적으로 업데이트하는 것보다 훨씬 빠르다.
• 시간 복잡도: 각 업데이트는 O(1) 시간에 수행된다. 전체 배열에 대한 누적 합 계산은 O(N) 시간이 소요된다

예시: 온도 조절

상황 : 7일 동안의 온도 기록을 가지고 있다. 각 날짜의 초기 온도는 0도로 설정되어 있다.

일:   1  2  3  4  5  6  7
온도: 0  0  0  0  0  0  0

이제 다음과 같은 온도 조절 작업을 수행한다고 가정해 보자 :
1. 2일부터 4일까지 매일 온도를 3도씩 올린다.
2. 5일부터 7일까지 매일 온도를 2도씩 올린다.

이 작업을 일반적인 방식으로 수행하려면 각 날짜의 온도를 개별적으로 업데이트해야 한다. 그러나 "+1-1 기법"을 사용하면 훨씬 더 효율적으로 처리할 수 있다.

 

+1-1 기법 적용

1. 초기 차분 배열:

  일:   1  2  3  4  5  6  7  8
  차분: 0  0  0  0  0  0  0  0

   배열의 크기는 8(N+1)로 설정한다. 이는 7(N)일간의 기록과 마지막에 추가적인 공간을 확보하기 위함이다. 2. 온도 조절

 

2. 명령 적용:

- 2일부터 4일까지 3도 올리기: `차분[2]`에 +3을 더하고, `차분[5]`에 -3을 더한다.

- 5일부터 7일까지 2도 올리기: `차분[5]`에 +2를 더하고, `차분[8]`에 -2를 더한다.

(from부터 시작해서 to+1전까지 올린다는 의미)

일:   1  2  3  4  5  6  7  8
차분: 0 +3  0  0 +2  0  0 -2

3. 누적 합 계산:

- 차분 배열에 누적 합을 적용하여 각 날짜의 최종 온도를 계산한다.

최종 온도 계산:

일:   1  2  3  4  5  6  7
온도: 0  3  3  3  5  5  5

결과

최종적으로, 각 날짜에 대한 온도는 다음과 같이 조절된다. 

- 2일부터 4일까지는 온도가 3도씩 올라, 3도가 된다.

- 5일부터 7일까지는 추가로 2도씩 올라, 총 5도가 된다.

이 예시에서 볼 수 있듯이, "+1-1 기법"은 반복적인 구간 업데이트를 효율적으로 처리하는 강력한 방법이다. 개별 요소를 일일이 업데이트하는 대신, 구간의 시작과 끝에만 변경을 적용하고 누적 합을 통해 최종 결과를 쉽게 얻을 수 있다.