누적 합
누적 합은 원소들의 앞부분 합을 저장해 연속 구간의 합을 빠르게 구하는 기법이다 배열 전처리·구간 질의 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할 수...
| 분류 | 알고리즘 · 배열 전처리·구간 질의 |
|---|---|
| 목적 | 원소들의 앞부분 합을 저장해 연속 구간의 합을 빠르게 구하는 기법이다 |
| 처리 방식 | P[0]=0, P[i+1]=P[i]+a[i]로 구성하고 반열린 구간 [l,r)의 합을 P[r]-P[l]로 계산한다 |
| 복잡도·성능 | 전처리 O(n), 구간 합 질의 O(1), 저장 O(n) |
| 필수 조건 | 덧셈과 역연산이 가능해야 하며 갱신이 빈번하면 자료구조를 달리 선택한다 |
| 참고 문헌 | 기술 참고 자료 |
| 관련 분야 | 알고리즘, 자료구조 |
누적 합은 원소들의 앞부분 합을 저장해 연속 구간의 합을 빠르게 구하는 기법이다 배열 전처리·구간 질의 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할 수 있다.[1]
처리 과정은 P[0]=0, P[i+1]=P[i]+a[i]로 구성하고 반열린 구간 [l,r)의 합을 P[r]-P[l]로 계산한다. 2차원 배열에는 포함 배제 원리를 이용한 누적 합을 적용할 수 있다. 실제 구현에서는 각 단계의 결과가 어떤 의미를 갖는지 불변식을 정하고, 입력·갱신·질의의 처리 경로를 구분한다.
성능은 전처리 O(n), 구간 합 질의 O(1), 저장 O(n) 올바르게 적용하려면 덧셈과 역연산이 가능해야 하며 갱신이 빈번하면 자료구조를 달리 선택한다 데이터의 범위와 해시·비교·수치 처리 규칙, 실패 시의 동작 등을 명확히 해야 구현체에 따라 결과가 달라지는 상황을 줄일 수 있다.
활용 및 관련 기법과 비교하면 배열 집계·이미지 적분 영상·구간 통계의 기초다. 자주 변경되는 배열에서는 펜윅 트리·세그먼트 트리를 사용할 수 있다. 성능 평가에서는 초기 자료구조 구성과 질의·갱신, 저장 공간을 분리하여 분석하고, 실제 하드웨어의 캐시 및 메모리 접근 비용도 함께 고려한다.[2]