누적합과 차분 배열

고정된 배열에서 구간 합을 O(1)에 구하는 누적합(Prefix Sum)과, 여러 구간에 값을 일괄로 더하는 작업을 O(1)에 처리하는 차분 배열(Difference Array) 기법입니다.

동작 과정

[ 누적합 — 구간 합 질의 ]

arr    = [ 3,  1,  4,  1,  5 ]   (index 0~4)
prefix = [ 0,  3,  4,  8,  9, 14 ]   (prefix[i] = arr[0..i-1]의 합, 길이 n+1)

구간 [1, 3]의 합 (arr[1]+arr[2]+arr[3] = 1+4+1 = 6) 을 구하려면:
  rangeSum(1, 3) = prefix[3+1] - prefix[1] = prefix[4] - prefix[1] = 9 - 3 = 6

[ 차분 배열 — 구간에 값 일괄 더하기 ]

초기 배열 (전부 0), 길이 5           : [ 0, 0, 0, 0, 0 ]
diff 배열 (길이 n+1)                 : [ 0, 0, 0, 0, 0, 0 ]

rangeAdd(1, 3, 5)  → index 1~3에 5를 더하고 싶다
  diff[1]     += 5   →  diff = [ 0, 5, 0, 0,  0, 0 ]
  diff[3 + 1] -= 5   →  diff = [ 0, 5, 0, 0, -5, 0 ]

reconstruct(): diff를 앞에서부터 누적합하며 채운다
  i=0: running=0+0=0   → arr[0]=0
  i=1: running=0+5=5   → arr[1]=5
  i=2: running=5+0=5   → arr[2]=5
  i=3: running=5+0=5   → arr[3]=5
  i=4: running=5-5=0   → arr[4]=0

결과 arr = [ 0, 5, 5, 5, 0 ]   ← index 1~3만 5가 더해졌다

누적합은 "값을 미리 쌓아 두고 두 지점의 차로 구간 합을 꺼내는" 방식이고, 차분 배열은 반대로 "변화량만 양 끝에 기록해 두고 나중에 한 번에 누적해 복원하는" 방식입니다. 둘은 같은 누적 연산을 서로 반대 방향으로 쓰는 짝입니다.

구현

// 누적합 — 구간 합을 O(1)에 구하기 위한 전처리
int[] buildPrefixSum(int[] arr) {
    int n = arr.length;
    int[] prefix = new int[n + 1];   // prefix[i] = arr[0..i-1]의 합
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    return prefix;
}

int rangeSum(int[] prefix, int left, int right) {  // arr[left..right] 구간 합, 0-indexed
    return prefix[right + 1] - prefix[left];
}

// 차분 배열 — 구간에 값을 일괄로 더하는 작업을 O(1)에 처리
int[] diff;

void initDiff(int n) {
    diff = new int[n + 1];
}

void rangeAdd(int left, int right, int value) {  // arr[left..right]에 value를 더함
    diff[left] += value;
    diff[right + 1] -= value;
}

int[] reconstruct(int n) {
    int[] arr = new int[n];
    int running = 0;
    for (int i = 0; i < n; i++) {
        running += diff[i];
        arr[i] = running;
    }
    return arr;
}

복잡도

구분전처리/갱신질의/복원근거
누적합O(n)O(1)prefix 배열을 한 번만 채우면 두 값의 차로 모든 구간 합을 꺼낼 수 있다
차분 배열O(1)O(n)구간 갱신마다 양 끝 두 칸만 수정, 전체 배열 복원은 한 번의 순회

둘 다 질의/갱신을 미리 모아 두고 한 번에 처리하는 오프라인 기법이라, 전처리 이후에는 원본 배열을 직접 건드리지 않는 것이 핵심입니다.

주의사항

핵심 정리

CSLOG에서 보기