구간 합 알고리즘 - 누적 합 배열

알고리즘 문제에서 종종 배열이나 리스트 내 특정 구간의 원소들의 합을 계산해야 할 때가 있을 것이다 이럴 때 쓰이는 알고리즘을 구간 합이라고 한다 이러한 구간 합 알고리즘에는 크게 누적 합 배열(prefix sum array)과 세그먼트 트리(segment tree)가 존재하는데

이번 글에선 이 중 그나마 이해하기 쉽다고 생각되는 누적 합 배열에 대해 소개하려고 한다

누적 합 배열 (Prefix Sum Array)이란?

누적 합 배열은 배열의 각 원소에 대해 해당 지점까지의 모든 원소들의 합을 저장한 배열로 이 방법의 핵심은 한 번의 배열 순회로 모든 누적 합을 계산한 후 이를 이용해 특정 구간의 합을 즉시 계산할 수 있다는 점이다

이해가 잘 안될 수 있으니 예시를 들어 설명하면

원본 배열: [3, 2, -1, 6, 5]

이러한 원본 배열이 있을 때

누적 합 배열: [3, 5, 4, 10, 15]

첫 번째 원소(3)부터 시작해서 각 단계에서 이전 단계의 누적 합에 현재 원소를 더한 누적 합 배열을 만들어주면

구간 합 = 누적 합 배열[4] - 누적 합 배열[1 - 1]
        = 15 - 3
        = 12

이런 식으로 누적 합 배열을 이용해서 원본 배열의 특정 구간의 합을 쉽게 계산할 수 있다

다음으로 누적 합 배열의 진행 순서를 살펴보면

1. 주어진 배열의 첫 번째 원소부터 시작하여, 각 원소에 대해 그 지점까지의 누적 합을 계산한다

2. 특정 구간 [i, j]의 합은 prefixSum[j] - prefixSum[i-1]로 계산할 수 있다 (여기서 prefixSum은 누적 합 배열을 뜻함)

이렇게 크게 초기화하는 1번 과정과 계산을 하는 2번 과정으로 두 가지 과정으로 나타낼 수 있다

장단점

누적 합 배열의 장점으로는

한 번의 누적 합 계산으로 여러 구간의 합을 빠르게 계산할 수 있다는 점과 코드 구현이 매우 간단하고 이해하기 쉽다는 점으로

다만 단점으로는 누적 합 배열을 만들기 위해 기존 배열과 동일한 크기의 추가적인 메모리 공간이 필요하다는 점과 원본 데이터가 변경되면 다시 누적 합 배열을 계산해야 하기에 데이터가 변경되는 경우에는 매우 비효율적으로 변한다

C++ 누적 합 배열 구현 코드

마지막으로 C++로 누적 합 배열 구현한 코드를 살펴보고 끝내겠다

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

vector<int> buildPrefixSum(const vector<int>& nums) {
    int n = nums.size();
    vector<int> prefixSum(n);
    prefixSum[0] = nums[0];
    for (int i = 1; i < n; ++i) {
        prefixSum[i] = prefixSum[i - 1] + nums[i];
    }
    return prefixSum;
}

int querySum(const vector<int>& prefixSum, int left, int right) {
    if (left == 0) return prefixSum[right];
    return prefixSum[right] - prefixSum[left - 1];
}

int main() {
    vector<int> nums = {3, 2, -1, 6, 5};
    vector<int> prefixSum = buildPrefixSum(nums);

    // 구간 합 계산 예시
    cout << "nums[1, 3] : " << querySum(prefixSum, 1, 3) << endl;

    return 0;
}