Skip to content

Frame

Prefix Sum

배열 앞부분 누적합으로 구간합을 빠르게 계산하는 기본 prefix sum 패턴과 N+1 길이 변형을 정리

Oct 16, 2025 — prefix-sum

prefix sum (N size)

prefixSum[i] = i 까지의 합.
prefixSum[i] = sum([arr[0], …, arra[i])

const prefixSum = Array(N).fill(0);
prefixSum[0] = arr[0];
for (let i = 1; i < N; i++) {
    prefixSum[i] = prefixSum[i - 1] + arr[i];
}

구간합 `[i, ..., j]`

prefixSum[i-1] 계산 시에 array out of bounds 에러가 발생할 수 있음.
prefixSum[j] - prefixSum[i] + arr[i] 이용 시에는 그러한 문제없이 이용 가능함.

sum([i, ..., j]) = prefixSum[j] - (prefixSum[i-1] ?? 0)
                 = prefixSum[j] - prefixSum[i] + arr[i]

참고 prefix sum : N+1 size

때로는 ith index 에 i전까지의 합 계산을 이용하는 겻이 더 편리한 경우도 있음.

prefixSumBefore[i] = i 전까지의 합.
prefixSumBefore[i] = sum([arr[0], …, arr[i-1])

const prefixSumBefore = Array(N+1).fill(0);
prefixSumBefore[0] = 0;
for (let i = 0; i < N; i += 1) {
    prefixSumBefore[i+1] = prefixSumBefore[i] + arr[i];
}

index            0 1  2  3  4  5
                 3 5  2 -2  4  1

prefixSum        3 8 10  8 12 13
prefixSumBefore  0 3  8 10  8 12 13

Reference