C++로 구현하는 배열 범위 합계 쿼리: 누적 합(Prefix Sum)을 활용한 효율적인 방법

이 글에서는 배열에서 인덱스 i부터 j까지의 요소 합계를 구하는 방법을 알아보겠습니다. 이를 흔히 범위 합계 쿼리(Range Sum Query)라고 부릅니다.

단순 반복문 방식의 한계

가장 직관적인 방법은 인덱스 i부터 j까지 반복문을 돌며 값을 하나씩 더하는 것입니다. 하지만 이런 범위 쿼리는 실제로 여러 번 반복해서 수행되는 경우가 많습니다. 매번 O(n) 시간이 걸리는 반복문을 실행하면 쿼리가 많아질수록 전체 처리 시간이 크게 늘어나 비효율적입니다.

누적 합을 활용한 해결 방법

이 문제를 더 효율적으로 해결하려면 누적 합(Cumulative Sum)을 미리 계산해 두는 것이 좋습니다. 누적 합 배열을 한 번만 만들어 두면, 이후 어떤 범위의 합계든 상수 시간 O(1) 안에 구할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

• 원본 배열의 각 위치까지의 합을 저장한 누적 합 배열 c_arr를 생성합니다.
• i가 0인 경우: c_arr[j]가 곧 0부터 j까지의 합입니다.
• i가 0이 아닌 경우: c_arr[j]에서 c_arr[i-1]을 빼면 i부터 j까지의 합이 됩니다.

알고리즘

rangeSum(arr, i, j)

begin
    c_arr := arr의 누적 합 배열
    if i = 0, then
        return c_arr[j]
    return c_arr[j] – c_arr[i-1]
end

C++ 구현 예제

#include<iostream>
using namespace std;

// 누적 합 배열 생성
void cumulativeSum(int c_arr[], int arr[], int n){
    c_arr[0] = arr[0];
    for(int i = 1; i<n; i++){
        c_arr[i] = arr[i] + c_arr[i-1];
    }
}

// 범위 합계 계산 (O(1))
int rangeSum(int c_arr[], int i, int j){
    if( i == 0){
        return c_arr[j];
    }
    return c_arr[j] - c_arr[i-1];
}

main() {
    int data[] = {5, 4, 32, 8, 74, 14, 23, 65};
    int n = sizeof(data)/sizeof(data[0]);
    int c_arr[n];
    cumulativeSum(c_arr, data, n); // 누적 합 미리 계산
    cout << "Range sum from index (2 to 5): " << rangeSum(c_arr, 2, 5) << endl;
    cout << "Range sum from index (0 to 3): " << rangeSum(c_arr, 0, 3) << endl;
    cout << "Range sum from index (4 to 7): " << rangeSum(c_arr, 4, 7) << endl;
}

실행 결과

Range sum from index (2 to 5): 128
Range sum from index (0 to 3): 49
Range sum from index (4 to 7): 176

시간 복잡도 분석

누적 합 배열을 만드는 데 처음 한 번 O(n)의 시간이 걸리지만, 그 이후에는 각 범위 합계 쿼리를 O(1)에 처리할 수 있습니다. 따라서 동일한 배열에 대해 범위 쿼리를 여러 번 수행해야 하는 상황이라면, 단순 반복문 방식(O(n) per query)에 비해 압도적으로 빠른 성능을 얻을 수 있습니다.

다만 이 방법은 배열이 갱신되지 않는 정적 데이터에 적합합니다. 만약 배열 요소가 자주 변경된다면 세그먼트 트리(Segment Tree)나 펜윅 트리(Fenwick Tree) 같은 자료구조를 고려하는 것이 좋습니다.