누적 합 Prefix Sum 원리: 구간 합 쿼리 O(1) 처리 비결

데이터 분석이나 대규모 로그 처리를 수행할 때, 특정 구간의 합을 구해야 하는 상황은 매우 흔하게 발생합니다. 배열의 특정 인덱스부터 다른 인덱스까지의 합을 매번 일일이 더하는 방식은 데이터의 크기가 커지고 쿼리의 횟수가 늘어날수록 시스템에 엄청난 부하를 줍니다. 이러한 비효율을 완벽하게 해결하고, 아무리 거대한 데이터라도 단 한 번의 연산으로 구간 합을 산출해내는 기법이 바로 누적 합(Prefix Sum)입니다. 본 포스팅에서는 누적 합의 수학적 원리와 1차원을 넘어 2차원 배열에서의 응용법을 2,500자 이상의 상세한 설명으로 정리해 보겠습니다.

1. 누적 합(Prefix Sum)의 정의와 전처리(Preprocessing)

누적 합의 핵심 아이디어는 '미리 계산해두기'에 있습니다. 원본 배열 A가 있을 때, 새로운 배열 S를 생성하여 S[i]에 A[0]부터 A[i]까지의 합을 미리 저장해두는 것입니다. 이를 전처리 단계라고 하며, 배열을 한 번 순회하는 것만으로 $O(N)$의 시간 복잡도 내에 모든 준비를 마칠 수 있습니다.

1-1. 구간 합을 구하는 수학적 마법: $O(1)$의 기적

일단 누적 합 배열 S가 완성되면, 어떤 구간 $[i, j]$의 합을 구하는 과정은 덧셈이 아닌 뺄셈 한 번으로 종료됩니다. 구간의 합은 S[j] - S[i-1]이라는 단순한 수식으로 도출됩니다. 이는 $i$부터 $j$까지의 합을 구하기 위해 0부터 $j$까지의 전체 합에서, 우리가 필요 없는 부분인 0부터 $i-1$까지의 합을 도려내는 논리입니다. 수만 개의 데이터를 매번 더해야 했던 작업이 상수 시간인 $O(1)$로 줄어드는 혁신적인 순간입니다.

2. 고난도 응용: 2차원 누적 합(2D Prefix Sum)

실전에서는 1차원 배열보다 2차원 평면에서의 구간 합(직사각형 영역의 합)을 구해야 하는 경우가 많습니다. 2차원 누적 합은 1차원의 원리를 평면으로 확장한 것으로, 포함과 배제의 원리(Inclusion-Exclusion Principle)를 정교하게 적용해야 합니다.

2-1. 2차원 누적 합 배열의 구축과 영역 계산

2차원 배열 S[i][j]는 (0, 0)부터 (i, j)까지의 직사각형 영역에 포함된 모든 원소의 합을 저장합니다. 특정 영역 $(x1, y1)$부터 $(x2, y2)$까지의 합을 구하려면 다음의 공식을 사용합니다.

$Sum = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]$

중복해서 빼버린 왼쪽 상단의 공통 영역을 다시 한 번 더해줌으로써 정확한 구간 합을 얻어내는 이 방식은, 이미지 프로세싱의 적분 영상(Integral Image) 기술이나 대규모 데이터 그리드 분석에서 필수적으로 사용됩니다.

3. 누적 합의 한계와 실무적 활용 시 주의사항

누적 합은 데이터가 고정되어 있을 때(Static Data) 최강의 효율을 발휘합니다. 만약 데이터가 수시로 업데이트되는 동적인 환경이라면, 값이 바뀔 때마다 누적 합 배열을 다시 갱신해야 하므로 비효율적입니다. 이러한 경우에는 펜윅 트리(Fenwick Tree)나 세그먼트 트리(Segment Tree)와 같은 고급 자료구조를 사용하는 것이 바람직합니다.

누적 합의 주요 활용 분야

로그 데이터 분석: 특정 시간대 사이의 트래픽 총량이나 매출 합계를 실시간으로 쿼리할 때.
이미지 처리: 필터 연산 시 특정 윈도우 내의 픽셀 값 평균을 고속으로 계산할 때.
게임 엔진: 넓은 맵 내의 특정 구역에 존재하는 오브젝트의 수치 합산이나 데미지 계산.


# 1차원 누적 합 Python 구현 예시
def get_prefix_sum(arr):
    n = len(arr)
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + arr[i]
    return prefix_sum

# 구간 [left, right]의 합 계산 (0-indexed 기준)
def query(prefix_sum, left, right):
    return prefix_sum[right + 1] - prefix_sum[left]

[누적 합 핵심 요약]
1. 원리: 배열의 합을 미리 전처리하여 구간 합 계산 시간을 $O(N)$에서 $O(1)$로 단축합니다.
2. 핵심: 전체 합에서 불필요한 앞부분의 합을 빼는 논리적 차이(Difference)를 이용합니다.
3. 적용: 데이터 변경이 적고 구간 합 조회 쿼리가 빈번한 시스템에 최적화된 기법입니다.

tech-korea