Algorithms/Prefix Sums

2.14.3 Difference Array

개념

인접한 값의 차이를 저장하는 배열입니다. D1=A1D_1=A_1, Di=Ai−Ai−1D_i=A_i-A_{i-1}로 정의하면 차분 배열의 누적 합으로 원래 배열을 복원할 수 있습니다.

구간에 같은 값 더하기

ll번째부터 rr번째까지 xx를 더하려면 DlD_l에 xx를 더하고 Dr+1D_{r+1}에서 xx를 뺍니다. 누적 합을 구할 때 ll부터 증가량이 적용되고 r+1r+1부터 상쇄됩니다.

모든 원소가 00이고 길이가 55인 배열에서 [2,4][2,4]에 33을 더하면 경계의 차분만 바뀌고, 복원 결과는 [0,3,3,3,0][0,3,3,3,0]입니다.

차분을 다시 더하면 (A1)+(A2−A1)+(A3−A2)=A3(A_1)+(A_2-A_1)+(A_3-A_2)=A_3처럼 중간 값이 상쇄됩니다. 이것이 누적 합으로 원래 값을 복원할 수 있는 이유입니다.

구간 전체에 xx를 더해도 구간 내부의 인접한 두 값의 차이는 (Ai+x)−(Ai−1+x)=Ai−Ai−1(A_i+x)-(A_{i-1}+x)=A_i-A_{i-1}로 같습니다. 왼쪽 경계는 앞 원소보다 xx만큼 더 커지고, 오른쪽 경계 다음은 앞 원소에 비해 xx만큼 작아지므로 두 경계의 차이만 바뀝니다.

위 예의 차분은 [0,3,0,0,−3][0,3,0,0,-3]입니다. 왼쪽부터 더하면 0,3,3,3,00,3,3,3,0이 되어 구간에만 33이 적용됩니다. 마지막 원소까지 갱신한다면 오른쪽 경계 다음 칸은 배열 바깥의 종료 표시로 생각할 수 있습니다.

이 방법은 여러 구간에 값을 더한 뒤 최종 배열을 한 번 구하는 문제에 적합합니다. 매 갱신 직후의 구간 합까지 필요하다면 복원 비용이 반복되므로 세그먼트 트리처럼 원소 수정과 구간 합 계산을 함께 처리하는 방법을 사용합니다.

복잡도

모든 갱신이 끝난 배열이 필요한 경우에 적합합니다. 원소 수를 NN, 갱신 수를 QQ라고 합니다.

연산시간복잡도공간복잡도
구간 갱신 기록O(1)O(1)추가 O(1)O(1)
최종 배열 복원O(N)O(N)차이 배열 O(N)O(N)
전체 갱신과 복원O(N+Q)O(N+Q)차이 배열 O(N)O(N)

예제

문제

처음에 모든 원소가 00인 배열에 구간 덧셈을 수행한 뒤 최종 배열을 구하여라.

입력

첫째 줄에 배열 길이 NN과 연산 수 QQ가 공백을 사이에 두고 주어진다. 1≤N,Q≤1001\le N,Q\le100이다.

다음 QQ개 줄에 구간의 양 끝 번호 l,rl,r과 더할 값 xx가 공백을 사이에 두고 주어진다. 1≤l≤r≤N1\le l\le r\le N; 1≤x≤1001\le x\le100이다. 번호가 ll부터 rr까지인 모든 원소에 xx를 더한다.

출력

최종 배열의 원소를 번호 순서대로 한 줄에 공백을 사이에 두고 출력한다.

예제 입력

5 2
2 4 3
1 2 1

예제 출력

1 4 3 3 0

예제 코드

C++20

#include <iostream>

using namespace std;

int d[102];

int main() {
    int n, q, i, l, r, x, s;

    cin >> n >> q;
    for (i = 0; i < q; ++i) {
        cin >> l >> r >> x;
        d[l] += x;
        d[r + 1] -= x;
    }
    s = 0;
    for (i = 1; i <= n; ++i) {
        s += d[i];
        cout << s << ' ';
    }
    cout << '\n';
}