LeetCode 303 - Range Sum Query - Immutable (Easy)

출처: https://leetcode.com/problems/range-sum-query-immutable/

// LeetCode 303 - Range Sum Query - Immutable (Easy)
// https://leetcode.com/problems/range-sum-query-immutable/

// 문제 설명
// 정수 배열 nums가 주어진다. 아래 쿼리를 처리하는 NumArray 클래스를 구현하라.
// sumRange(left, right): nums[left] + ... + nums[right] (양 끝 포함)의 합을 반환.
// 배열은 불변(immutable)이고 sumRange가 여러 번 호출된다.

// 제약 조건
// 1 <= nums.length <= 10^4
// -10^5 <= nums[i] <= 10^5
// 0 <= left <= right < nums.length
// sumRange 호출 최대 10^4회

// Example
// Input : ["NumArray","sumRange","sumRange","sumRange"]
//         [[[-2,0,3,-5,2,-1]],[0,2],[2,5],[0,5]]
// Output: [null,1,-1,-3]
//   sumRange(0,2) = -2+0+3      =  1
//   sumRange(2,5) = 3-5+2-1     = -1
//   sumRange(0,5) = -2+0+3-5+2-1 = -3

// 접근 — 프리픽스 합(prefix sum) 전처리
// 쿼리마다 구간을 직접 더하면 O(n) x 10^4회 = 최악 10^8 연산 — 전처리로 없앤다.
// 1) 생성자에서 누적합 배열 p를 만든다. p[i] = nums[0..i-1]의 합, p[0] = 0.
// 2) 구간 합은 뺄셈 한 번: sumRange(l, r) = p[r+1] - p[l].
// 3) p를 n+1 크기(빈 접두사 포함)로 잡으면 l = 0일 때의 예외 분기가 사라진다.
// 시간: 전처리 O(n) + 쿼리 O(1), 공간 O(n)

#include <vector>
using namespace std;

class NumArray {
    vector<int> p;                                    // p[i] = 앞에서 i개의 합
public:
    NumArray(vector<int>& nums)
    {
        p.assign(nums.size() + 1, 0);
        for (int i = 0; i < (int)nums.size(); ++i)
            p[i + 1] = p[i] + nums[i];                // 누적합 전처리
    }

    int sumRange(int left, int right)
    {
        return p[right + 1] - p[left];                // 구간 합 = 누적합의 차
    }
};

정리

• “배열이 불변 + 구간 합 쿼리가 반복” — 이 조합이 프리픽스 합의 신호다. 쿼리마다 직접 더하면 O(n)×10^4회로 최악 10^8 연산이지만, 전처리 O(n) 한 번이면 이후 모든 쿼리가 뺄셈 한 번(O(1))으로 끝난다. 문제 제목의 Immutable이 이 설계의 전제 — 원소가 바뀌는 순간 누적합 전체가 무효가 된다.
• p를 n+1 크기로 잡고 p[0] = 0(빈 접두사)을 padding하는 게 관용구다. sumRange(0, r)처럼 왼쪽 끝이 0인 쿼리에서 if (left == 0) 분기가 통째로 사라진다. BFS에서 visited를 +1 인코딩으로 두고 출력 때 -1 하던 것과 같은 “경계를 패딩으로 지우는” 발상.
• 자료형 점검: 누적합의 상한은 10^4 × 10^5 = 10^9로 int 최대(약 2.1×10^9) 안쪽이라 int로 충분하다. 원소 범위나 길이가 한 자리만 더 컸어도 long long — 행렬의 곱셈 때처럼 누적값 상한부터 계산하고 자료형을 정하는 습관.
• 쿼리형 클래스 설계 문제의 틀: 생성자 = 전처리, 멤버 함수 = O(1) 조회. 이 구조를 기억해 두면 시리즈 후속(Range Sum Query 2D, Mutable — 세그먼트 트리)에서 무엇이 달라지는지가 보인다.
• 검증: 예제 [-2,0,3,-5,2,-1]의 세 쿼리(1, -1, -3)와 단일 원소 쿼리 sumRange(3,3) = -5 통과 (MSVC /std:c++17 컴파일·실행).