범위 합계 쿼리(Range Sum Query - Immutable) - C++ 풀이

정수 배열이 주어지고, 특정 구간 [i, j]에 포함된 요소들의 합을 구하는 문제를 생각해 보겠습니다. 이 문제에서는 두 가지 조건을 염두에 두어야 합니다. 첫째, 배열은 불변(immutable)이므로 생성 이후 요소 값이 변경되지 않으며, 둘째, 같은 형태의 구간 합 쿼리가 여러 번 반복해서 들어옵니다. 따라서 쿼리 개수가 많아질 때 실행 시간을 효율적으로 관리하는 것이 핵심입니다.

예를 들어 배열이 A = [5, 8, 3, 6, 1, 2, 5]라고 할 때, 쿼리 (A, 0, 3)의 결과는 5 + 8 + 3 + 6 = 22가 됩니다.

문제 해결 접근법

이 문제는 누적 합(Prefix Sum) 기법을 사용하면 효율적으로 해결할 수 있습니다. 절차는 다음과 같습니다.

• 새로운 배열 B를 준비합니다. B[i]에는 원본 배열의 인덱스 0부터 i까지의 요소 합이 저장됩니다.
• 구간 합 쿼리 (i, j)가 들어오면 B[j] − B[i − 1]을 계산하여 반환합니다.

생성자에서 누적 합 배열을 만드는 데 O(n)의 시간이 걸리지만, 한 번 전처리를 마치면 이후 모든 쿼리를 O(1) 상수 시간에 처리할 수 있습니다. 따라서 쿼리가 수천, 수만 번 들어오는 상황에서도 빠른 응답이 가능합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class NumArray {
    public:
    vector<int> pre;
    NumArray(vector<int>& nums) {
        pre.clear();
        int n = nums.size();
        pre.resize(n);
        for(int i = 0; i < n; i++){
            if(i == 0) pre[0] = nums[0];
            else
            pre[i] = pre[i - 1] + nums[i];
        }
    }
    int sumRange(int i, int j) {
        if(i == 0) return pre[j];
        return pre[j] - pre[i - 1];
    }
};
main(){
    vector<int> v = {5,8,3,6,1,2,5};
    NumArray na(v);
    cout<<na.sumRange(0,2)<<endl;
    cout<<na.sumRange(2,5)<<endl;
    cout<<na.sumRange(0,5)<<endl;
}

입력

[5,8,3,6,1,2,5]로 초기화한 뒤
sumRange(0,2)
sumRange(2,5)
sumRange(0,5) 호출

출력

16
12
25

sumRange(0, 2)는 5 + 8 + 3 = 16, sumRange(2, 5)는 3 + 6 + 1 + 2 = 12, sumRange(0, 5)는 5 + 8 + 3 + 6 + 1 + 2 = 25로, 각 쿼리가 상수 시간 안에 정확하게 처리되는 것을 확인할 수 있습니다.