📚 단일 패턴

303. Range Sum Query - Immutable

Prefix sum 배열을 전처리해 구간 합 계산하는 불변 범위 합 문제

Oct 22, 2025 — prefix-sum

문제 설명

LeetCode 303. Range Sum Query - Immutable (opens in a new window)
배열을 주고, 주어진 구간합을 계산하는 문제

풀이 아이디어

구간합 계산하는 간단한 문제.
Immutable 구간합은 prefix sum 으로 해결 가능.
그렇다면 mutable 구간합 은 어떻게 계산할까 ?
- Segment Tree : 범위 최솟값, 최댓값 등 다양한 쿼리에 확장 가능
- Fenwick Tree : 구현이 간단하고 메모리 효율적, 합 계산에 특화

해결 전략

Prefix Sum

풀이

우리의 prefixSum 필살기 : prefixSum[i-1] 신경쓰지 않고 계산할 수 있음.

// sum [ i ... j ]
prefixSum[j] - prefixSum[i] + nums[i]

구현

class NumArray {
    private nums: number[]
    private prefixSum: number[];

    constructor(nums: number[]) {
        this.nums = nums;
        this.prefixSum = Array(nums.length).fill(0);
        this.prefixSum[0] = nums[0];
        for (let i = 1; i < nums.length; i += 1) {
            this.prefixSum[i] = this.prefixSum[i-1] + nums[i];
        }
    }

    sumRange(left: number, right: number): number {
        return this.prefixSum[right] - this.prefixSum[left] + this.nums[left];
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * var obj = new NumArray(nums)
 * var param_1 = obj.sumRange(left,right)
 */