누적합(Prefix Sum)

목차

• 누적합(Prefix Sum)이란?
• 누적합의 기본 원리
• 누적합의 활용 사례
• 누적합과 다른 알고리즘 비교
  • 차이 배열 (Difference Array)
  • 슬라이딩 윈도우 기법
  • 세그먼트 트리 / BIT(펜윅 트리)
• 기본 구현 (코드 예제)
  • 1차원 누적합
  • 2차원 누적합
• 결론 및 정리

 

1. 누적합 이란?

 

누적합은 배열의 시작부터 특정 인덱스까지의 합을 미리 계산하여 저장한 배열이다.

• 특정 구간의 합을 구하기 위해서는 해당 구간의 끝 지점까지의 누적합에서 시작 지점까지의 누적합을 빼면 된다.
• 반복적인 구간 합 계산을 O(1) 시간에 처리할 수 있다.
• 예시: 
  주어진 배열 arr = [a₀, a₁, a₂, ..., aₙ₋₁]에 대해
  prefix[i] = a₀ + a₁ + ... + aᵢ (보통 인덱스 0부터 시작하는 경우) 또는 prefix[0] = 0로 시작할 수도 있다.

---

2. 누적합의 기본 원리

• 계산 과정:
  • 초기값 설정: 보통 prefix[0] = 0 (또는 배열의 첫 번째 값을 그대로 할당)
  • 점화식: prefix[i+1] = prefix[i] + arr[i]
• 장점:
  • 구간 합 쿼리를 O(1)에 처리 가능 → 여러 번 구간 합을 구하는 문제에 엄청 유용.
  • 전처리 한 번이면 쿼리마다 빠른 계산 가능.
• 주의할 점:
  • 데이터가 변화하는 경우에는 누적합을 매번 재계산해야 하므로, 업데이트가 잦은 경우에는 세그먼트 트리나 펜윅 트리를 고려하는 것이 좋다.

---

3. 누적합의 활용 사례

 

• 구간 합 구하기
  • 예: “l부터 r까지의 합”을 반복적으로 물어보는 문제.
  • 누적합 배열만 있으면 prefix[r+1] - prefix[l]로 바로 해결 가능.
• 2차원 누적합(적분 이미지)
  • 이미지 처리에서 특정 영역 픽셀 합을 빠르게 구하고 싶을 때 사용.
• 누적 통계/분석
  • 시간대별 누적 데이터 구하기, 구간 평균, 누적 평균 등도 쉽게 처리할 수 있다.

 

---

4. 누적합과 다른 알고리즘 비교

 

4.1 차이 배열 (Difference Array)

• 특징: 구간 업데이트(예: l~r 구간에 일정 값 더하기)에 최적화된 자료구조.
• 차이점: 누적합은 구간 합 쿼리, 차이 배열은 구간 업데이트에 강점.
• 사용 예: “구간에 여러 번 +1, -1” 같은 연산 후, 최종 배열을 구하는 문제.

4.2 슬라이딩 윈도우 기법

• 특징: 고정 크기의 연속 구간 합(또는 평균)을 구하면서 윈도우를 한 칸씩 옮길 때, O(1)로 계산 가능하게 만든 기법.
• 누적합과 결합: 누적합 배열을 사용하면 슬라이딩 윈도우의 합을 더욱 간단히 구할 수 있어.

4.3 세그먼트 트리 / BIT(펜윅 트리)

• 특징: 구간 합 쿼리와 구간 업데이트가 모두 빈번할 때 사용하면 효율적.
• 누적합과의 차이: 누적합은 정적 배열에 적합, 세그먼트 트리는 동적(수정) 쿼리에 최적.

자료구조구간 합 쿼리업데이트전처리메모리(대략)

자료구조	구간 합 쿼리	업데이트	전처리	메모리 (대략)
누적합(prefix sum)	O(1)	O(N)	O(N)	O(N)
세그먼트 트리	O(log N)	O(log N)	O(N)	O(4N) ~ 일반적으로
펜윅 트리(BIT)	O(log N)	O(log N)	O(N)	O(N)

---

5. 기본 구현

• 1차원 누적합

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n), prefix(n + 1, 0);

    // 배열 입력
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    
    // 누적합 계산: prefix[0] = 0
    for (int i = 0; i < n; ++i) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    
    // 구간 합 계산: 예를 들어, 구간 [l, r]의 합
    int l, r;
    cin >> l >> r; // l, r은 0-based index
    int rangeSum = prefix[r + 1] - prefix[l];
    cout << "구간 합: " << rangeSum << "\n";
    
    return 0;
}

 

 

• prefix[0] = 0으로 시작해서, i번째 값을 더하면서 누적합을 구함.
• 구간 [l, r] 합은 prefix[r+1] - prefix[l]로 구할 수 있다.

 

• 2차원 누적합

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m; 
    vector<vector<int>> arr(n, vector<int>(m));

    // 행렬 입력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }

    // 2차원 누적합 배열(prefix) 생성 (크기: (n+1) x (m+1))
    // prefix[i][j]는 (0,0)부터 (i-1, j-1)까지의 합을 의미
    vector<vector<int>> prefix(n + 1, vector<int>(m + 1, 0));

    // 누적합 계산
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            prefix[i + 1][j + 1] = prefix[i][j + 1] 
                                 + prefix[i + 1][j] 
                                 - prefix[i][j] 
                                 + arr[i][j];
        }
    }

    // 예: 구간 합 쿼리 - (r1, c1)부터 (r2, c2)까지의 합 구하기
    // (0-based index 가정)
    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;

    // 2차원 구간 합 공식
    int subMatrixSum = prefix[r2 + 1][c2 + 1] 
                     - prefix[r1][c2 + 1] 
                     - prefix[r2 + 1][c1] 
                     + prefix[r1][c1];

    cout << "서브 행렬 합: " << subMatrixSum << "\n";

    return 0;
}

 

• prefix[i+1][j+1]에 (0,0)부터 (i,j)까지의 합을 저장한다.
  • 이를 위해 “위쪽 누적합 + 왼쪽 누적합 - 겹치는 부분 + 현재 원소(arr[i][j])”를 더하는 방식이다.
• 서브 행렬 합을 구할 때는 원하는 구간의 “우상단, 좌상단, 우하단, 좌하단” 부분을 적절히 더하고 빼서 구한다.

 

---

6. 결론 및 정리

• 요약
  • 간단하지만 구간 합 문제에서 매우 효율적
  • 반복되는 구간 합 계산을 O(1)에 처리해주기 때문에, 쿼리가 많을수록 효율이 높다.
• 알아둘 점
  • 배열 값 변경이 잦으면 누적합을 매번 다시 만들어야 해서 비효율적일 수 있다.
  • 그럴 땐 세그먼트 트리나 펜윅 트리 같은 다른 자료구조 고민해 보는 게 좋다.