Prefix Sum은 어떤 문제를 빠르게 해결하나요?

Prefix Sum은 배열의 앞에서부터 누적합을 미리 계산해 구간 합을 O(1)에 구하는 기법입니다. 같은 배열에 대해 구간 합 질의가 여러 번 들어올 때 매번 합을 다시 계산하는 비용을 크게 줄입니다.

핵심 개념

• prefix[i]를 0번부터 i-1번까지의 합으로 두면 구간 [l, r)의 합은 prefix[r] - prefix[l]입니다.
• 2차원 배열에서도 누적합을 만들면 사각형 영역 합을 빠르게 구할 수 있습니다.
• 업데이트가 거의 없는 정적 데이터에 특히 적합합니다.

동작 방식 또는 판단 기준

이 주제를 이해할 때는 다음 순서로 보면 실무 적용이 쉬워집니다.

1. 무엇을 해결하려는가: 성능, 표현력, 안정성, 접근성 중 어떤 문제를 줄이려는지 확인합니다.
2. 전제 조건은 무엇인가: 정렬 여부, 브라우저 지원, 네트워크 특성, 동시성 조건처럼 성립해야 하는 조건을 점검합니다.
3. 비용은 어디서 발생하는가: 시간 복잡도, 메모리, 캐시, 재시도, 렌더링 비용처럼 병목 지점을 나눠 봅니다.
4. 실패 시 어떤 문제가 생기는가: 잘못 적용했을 때의 버그나 운영 리스크를 함께 고려합니다.

실제 예시

const arr = [2, 4, 1, 7];
const prefix = [0];
for (const x of arr) prefix.push(prefix[prefix.length - 1] + x);

function rangeSum(l, r) { // [l, r)
  return prefix[r] - prefix[l];
}

rangeSum(1, 3); // arr[1] + arr[2] = 5

부분 배열 합이 K인 개수:
현재 누적합 sum에 대해 과거에 sum-K가 몇 번 나왔는지 Hash Map으로 세면 O(n)

실무에서 주의할 점

• 원소 업데이트가 잦으면 prefix sum을 다시 계산해야 하므로 비효율적입니다. 이때는 Fenwick Tree나 Segment Tree를 고려합니다.
• inclusive/exclusive 인덱스 규칙을 섞으면 off-by-one 버그가 자주 납니다.
• 합이 커질 수 있으면 정수 overflow를 고려해야 합니다.

실무 적용 가이드

• 구간 합 질의가 많고 데이터 변경이 적으면 Prefix Sum을 먼저 검토합니다.
• 누적합 배열의 첫 값을 0으로 두면 빈 구간과 경계 처리가 쉬워집니다.
• 카운팅 문제에서는 누적합 + Hash Map 조합을 자주 사용합니다.

함께 연결해서 보면 좋은 키워드

Prefix Sum, Range Sum, Cumulative Sum, Fenwick Tree

정리

Prefix Sum은 배열의 앞에서부터 누적합을 미리 계산해 구간 합을 O(1)에 구하는 기법입니다. 다만 개념 자체보다 중요한 것은 적용 조건과 한계를 함께 이해하는 것입니다. 작은 예제에서는 단순해 보여도 실제 서비스에서는 성능, 보안, 유지보수성, 접근성 요구사항이 함께 얽히므로, 문제의 성격을 먼저 파악한 뒤 적절한 도구로 선택하는 것이 좋습니다.