---
id: "lessons/prefix-sum-difference"
title: "누적합과 차분 배열: 구간을 한 번에 처리하기"
description: "구간 합과 구간 덧셈을 분리하고, 경계 표시를 실제 값으로 복원합니다."
kind: "record"
published: "2026-10-04T00:00:00.000Z"
tags: ["알고리즘","C++","기본기"]
url: "https://www.readiz.com/records/prefix-sum-difference/"
markdownUrl: "https://www.readiz.com/records/prefix-sum-difference/index.md"
---

# 누적합과 차분 배열: 구간을 한 번에 처리하기

누적합은 배열의 앞에서부터 합을 미리 저장해 두고, 구간 합을 빠르게 꺼내는 기법입니다. 차분 배열은 반대로 여러 구간에 값을 더하는 작업을 표시만 해 두었다가 마지막에 한 번에 실제 값을 복원하는 기법입니다.

두 기법은 모두 "구간을 매번 직접 훑지 않는다"는 생각에서 출발합니다.

```text
구간 합을 많이 물어본다 -> 누적합
구간 업데이트를 많이 한 뒤 최종 배열만 필요하다 -> 차분 배열
격자 직사각형 합을 많이 물어본다 -> 2차원 누적합
격자 직사각형 업데이트를 많이 모은다 -> 2차원 차분 배열
```

Fenwick Tree나 Segment Tree보다 단순하지만, 업데이트와 질의가 섞이지 않는 문제에서는 더 빠르고 구현도 짧습니다.

## 1차원 누적합

배열 `a`가 있을 때 `prefix[i]`를 `a[0]`부터 `a[i - 1]`까지의 합으로 정의합니다. 즉 `prefix[0] = 0`이고, `prefix`의 길이는 `n + 1`입니다.

```text
a:       3   1   4   1   5
prefix:  0   3   4   8   9   14
index:   0   1   2   3   4    5
```

이렇게 잡으면 0-indexed 구간 `[l, r]`의 합은 아래처럼 구합니다.

```text
sum(l, r) = prefix[r + 1] - prefix[l]
```

예를 들어 `a[1] + a[2] + a[3] = 1 + 4 + 1 = 6`입니다.

```text
prefix[4] - prefix[1] = 9 - 3 = 6
```

## 구현

`prefix[i]`에는 앞의 `i`개 원소 합을 저장합니다. `prefix[0] = 0`을 두면 `l = 0`인 구간도 같은 식으로 계산할 수 있습니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp
#include <tuple>
#include <vector>
using namespace std;

vector<long long> buildPrefix(const vector<int>& a) {
    int n = (int)a.size();
    vector<long long> prefix(n + 1, 0);

    for (int i = 0; i < n; ++i) {
        prefix[i + 1] = prefix[i] + a[i];
    }
    return prefix;
}

long long rangeSum(const vector<long long>& prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}
```

구간은 0부터 시작하는 양 끝 포함 `[l, r]`입니다. 입력이 1부터 시작하면 두 끝에서 1을 뺍니다. 빈 구간을 허용하는 호출부에서는 `l > r`일 때 0을 반환하도록 처리합니다.

누적합을 한 번 만드는 데 `O(n)`, 이후 구간 하나는 `O(1)`이므로 질의 `q`개의 총비용은 `O(n + q)`입니다.

## 차분 배열

차분 배열은 인접한 값의 차이를 저장합니다.

```text
a:    3   1   4   1   5
diff: 3  -2   3  -3   4
```

`diff[0] = a[0]`이고, `diff[i] = a[i] - a[i - 1]`입니다. 이 차분 배열의 누적합을 다시 구하면 원래 배열이 복원됩니다.

```text
3
3 + (-2) = 1
1 + 3 = 4
4 + (-3) = 1
1 + 4 = 5
```

차분 배열의 장점은 구간에 값을 더할 때 나타납니다.

```text
a[l]부터 a[r]까지 x를 더하고 싶다.
```

이 작업은 차분 배열에서 두 곳만 바꾸면 됩니다.

```text
diff[l] += x
diff[r + 1] -= x
```

`l`부터 값이 x만큼 올라가고, `r + 1`부터 다시 x만큼 내려가도록 표시하는 것입니다.

## 구간 업데이트를 모아서 적용하기

`diff`에 업데이트만 모은 뒤 누적해서 원래 배열에 더합니다. 처음부터 0인 배열도 같은 코드에 넣을 수 있습니다.

```cpp
vector<long long> addRangesToArray(
    const vector<long long>& a,
    const vector<tuple<int, int, long long>>& queries
) {
    int n = (int)a.size();
    vector<long long> diff(n + 1, 0);

    for (auto [l, r, value] : queries) {
        diff[l] += value;
        diff[r + 1] -= value;
    }

    vector<long long> result(n);
    long long extra = 0;
    for (int i = 0; i < n; ++i) {
        extra += diff[i];
        result[i] = a[i] + extra;
    }
    return result;
}
```

업데이트 `q`개를 기록하고 최종 배열을 복원하는 데 `O(q + n)`이 듭니다. 중간 상태의 구간 합을 묻는 질의가 섞이면 이 방식만으로는 처리할 수 없습니다.

시간 구간을 `[start, end)`로 표현한다면 종료 표시는 `end + 1`이 아니라 `end`에 둡니다. 모든 업데이트가 끝난 뒤 합 질의만 남는다면 복원한 배열의 누적합을 만들면 됩니다.

## 2차원 누적합

격자에서 직사각형 합을 많이 물어보면 2차원 누적합을 씁니다.

`prefix[y][x]`를 왼쪽 위부터 `(y - 1, x - 1)`까지의 직사각형 합으로 정의합니다. 모든 행의 길이가 같은 직사각형 격자를 받으며, 배열 크기는 `(h + 1) x (w + 1)`로 둡니다.

```cpp
vector<vector<long long>> buildPrefix2D(const vector<vector<int>>& grid) {
    int h = (int)grid.size();
    int w = h == 0 ? 0 : (int)grid[0].size();
    vector<vector<long long>> prefix(h + 1, vector<long long>(w + 1, 0));

    for (int y = 0; y < h; ++y) {
        for (int x = 0; x < w; ++x) {
            prefix[y + 1][x + 1] =
                prefix[y][x + 1]
                + prefix[y + 1][x]
                - prefix[y][x]
                + grid[y][x];
        }
    }
    return prefix;
}
```

`prefix[y][x]`가 두 번 더해지는 영역을 한 번 빼는 것이 핵심입니다.

## 2차원 직사각형 합

[2차원 누적합: 더하고 빼는 영역 따라가기](https://www.readiz.com/learn/lab/?demo=prefix-sum)

질의 직사각형을 바꾸고 네 항을 한 단계씩 적용해 보세요. 중복으로 뺀 왼쪽 위 영역을 마지막에 되돌리면, 선택한 직사각형의 셀만 한 번씩 남습니다. 데모의 반열린 구간 `[r1, r2) × [c1, c2)`에서 `r2`, `c2`는 아래 양끝 포함 코드의 `y2 + 1`, `x2 + 1`에 해당합니다.

위쪽 행 `y1`, 아래쪽 행 `y2`, 왼쪽 열 `x1`, 오른쪽 열 `x2`가 모두 0-indexed이고 양 끝 포함이라고 하겠습니다.

```cpp
long long rectSum(
    const vector<vector<long long>>& prefix,
    int y1,
    int x1,
    int y2,
    int x2
) {
    return prefix[y2 + 1][x2 + 1]
        - prefix[y1][x2 + 1]
        - prefix[y2 + 1][x1]
        + prefix[y1][x1];
}
```

그림으로 생각하면 큰 직사각형에서 위쪽과 왼쪽을 빼고, 두 번 빠진 왼쪽 위를 다시 더합니다.

```text
answer = 전체 - 위쪽 - 왼쪽 + 왼쪽 위 중복 영역
```

2차원 누적합도 질의는 `O(1)`입니다. 전처리는 `O(hw)`입니다.

## 2차원 차분 배열

여러 직사각형에 값을 더한 뒤 최종 격자만 필요할 때 씁니다. `(y1, x1)`에서 증가를 시작하고, 아래쪽과 오른쪽 경계 다음 칸에서 각각 취소합니다. 두 번 취소된 오른쪽 아래 영역은 한 번 더해 복구합니다.

```cpp
#include <tuple>
#include <vector>
using namespace std;

vector<vector<long long>> applyRectAdds(
    int h,
    int w,
    const vector<tuple<int, int, int, int, long long>>& queries
) {
    vector<vector<long long>> diff(h + 1, vector<long long>(w + 1, 0));

    for (auto [y1, x1, y2, x2, value] : queries) {
        diff[y1][x1] += value;
        diff[y2 + 1][x1] -= value;
        diff[y1][x2 + 1] -= value;
        diff[y2 + 1][x2 + 1] += value;
    }

    vector<vector<long long>> result(h, vector<long long>(w, 0));
    for (int y = 0; y < h; ++y) {
        for (int x = 0; x < w; ++x) {
            long long value = diff[y][x];
            if (y > 0) value += result[y - 1][x];
            if (x > 0) value += result[y][x - 1];
            if (y > 0 && x > 0) value -= result[y - 1][x - 1];
            result[y][x] = value;
        }
    }
    return result;
}
```

`diff`를 `(h + 1) × (w + 1)`로 만들면 `y2 + 1 == h`나 `x2 + 1 == w`인 표시도 안전합니다. 최종 결과는 `h × w`만 사용합니다.

## 로컬 연습: 구간을 모두 갱신한 뒤 합 질의

배열에 M개의 구간 덧셈을 모두 적용한 뒤 Q개의 구간 합을 구하세요. 모든 구간은 0-based \[l,r)이며 빈 구간도 허용합니다.

**입력:** N M Q, 길이 N의 초기 배열, M줄의 l r delta, Q줄의 l r 순서입니다. 1 <= N <= 200000, 0 <= M,Q <= 200000, |원소|,|delta| <= 1000000, 0 <= l <= r <= N입니다.

**출력:** 각 질의의 합을 한 줄씩 출력합니다.

### 예시

```text exercise=prefix-sum-difference role=input
5 2 3
2 -1 3 0 4
1 4 2
0 2 -1
0 5
1 4
2 2
```

```text exercise=prefix-sum-difference role=output
12
7
0
```

**확인 방법:** 차분으로 갱신을 모은 뒤 복원한 배열은 \[1,0,5,2,4]입니다. 그 배열의 누적합으로 질의합니다. N <= 20에서는 원소별 갱신·직접 합산과 비교하고, l=r과 r=N을 검사합니다.

## 경계 표시를 직접 복원하기

![초기 배열 2,-1,3,0,4에 두 업데이트를 표시합니다. 차분 -1,2,1,0,-2,0을 누적하면 추가량 -1,1,2,2,0이 되고, 최종 배열은 1,0,5,2,4입니다.](https://www.readiz.com/assets/lessons/array-ranges/difference.svg)

[차분의 표시와 복원을 한 단계씩 보기](https://www.readiz.com/learn/explore/?demo=difference)

본문 함수는 양 끝을 포함하는 `[l, r]`을 받지만, 로컬 연습과 새 데모는 오른쪽 끝을 제외하는 `[l, r)`을 씁니다. `[1, 4)`에 2를 더한다면 `diff[1] += 2`, `diff[4] -= 2`입니다. 빈 구간은 아무 값도 바꾸지 않으며 `r = N` 표시는 길이 `N + 1`인 차분 배열의 마지막 칸에 안전하게 기록합니다.

## 완성 파일로 실행하기

[C++17 전체 예제 내려받기](https://www.readiz.com/assets/lessons/array-ranges/prefix-sum-difference.cpp)

위의 로컬 연습 입력을 `input.txt`에 저장합니다. 파일에는 본문 함수와 별도로, 64비트 복원 배열에서 누적합을 만드는 `main`이 들어 있습니다. 모든 갱신이 끝난 뒤에만 질의하므로 중간 상태의 질의는 지원하지 않습니다.

```sh
c++ -std=c++17 -O2 prefix-sum-difference.cpp -o prefix-demo
./prefix-demo < input.txt
```

출력은 차례대로 `12`, `7`, `0`입니다. 초기 원소는 작아도 여러 갱신과 긴 구간의 합은 `int` 범위를 넘을 수 있으므로 복원값과 합은 `long long`으로 계산합니다.