업데이트 없이 범위 합계 쿼리를 처리하는 C++ 프로그램: 접두사 합(Prefix Sum) 완벽 가이드

배열에서 인덱스 i부터 j까지의 요소 합계를 계산해야 하는 상황을 생각해 봅시다. 문제는 이러한 쿼리가 여러 번 반복해서 실행될 수 있다는 점입니다. 매번 반복문으로 구간을 순회하면 비효율적이기 때문에, 접두사 합(Prefix Sum) 배열을 활용하면 각 쿼리를 상수 시간에 처리할 수 있습니다.

입력 및 출력 예시

입력: arr[] = {5, 6, 3, 4, 1}, i = 1, j = 3
출력: 13

동작 원리 설명

인덱스 1부터 3까지의 요소는 6, 3, 4이므로 합계는 다음과 같습니다.

6 + 3 + 4 = 13

가장 단순한 방법은 i부터 j까지 반복문을 돌며 요소를 더하는 것이지만, 쿼리가 많아지면 시간 복잡도가 커집니다. 그래서 원본 배열을 수정하지 않고 누적합 배열을 미리 만들어 두는 방식을 사용합니다.

sum[0] = 5
sum[1] = 6 + 5 = 11
sum[2] = 3 + 6 + 5 = 14
sum[3] = 4 + 3 + 6 + 5 = 18
sum[4] = 1 + 4 + 3 + 6 + 5 = 19

sum[] = {5, 11, 14, 18, 19}

이렇게 만든 누적합 배열에서 구간 [i, j]의 합계는 다음 공식으로 한 번에 구할 수 있습니다.

sum[j] - sum[i - 1]
= sum[3] - sum[0]
= 18 - 5
= 13

i가 0인 경우에는 앞에 뺄 값이 없으므로 sum[j]를 그대로 반환하면 됩니다.

C++ 구현 코드

#include <iostream>
using namespace std;

int rangeSum(int i, int j, int sum[]) {
    if (i == 0)
        return sum[j];
    return sum[j] - sum[i - 1];
}

int main() {
    int arr[] = { 5, 6, 3, 4, 1 };
    int n = 5;
    int sum[5];

    // 접두사 합 배열 생성
    sum[0] = arr[0];
    for (int i = 1; i < n; i++) {
        sum[i] = arr[i] + sum[i - 1];
    }

    cout << rangeSum(1, 3, sum) << endl;
    return 0;
}

실행 결과

13

시간 복잡도 분석

• 전처리(누적합 배열 생성): O(n)
• 각 범위 합계 쿼리: O(1)
• 공간 복잡도: O(n) — 누적합 배열 저장용

이처럼 배열의 값이 업데이트되지 않는 정적 데이터라면, 접두사 합 배열을 한 번만 계산해 두고 여러 쿼리를 즉시 처리하는 것이 가장 효율적인 접근 방식입니다.