누적 합은 시작부터 각 위치까지의 합을 미리 저장하여 구간 합 질의를 빠르게 처리하는 방법이다.
원리
P[0]=0, P[i+1]=P[i]+A[i]로 두면 반열린 구간 [l,r)의 합은 P[r]−P[l]이다. 전처리 O(n) 후 질의 하나를 O(1)에 처리한다.
예시
배열 3, 1, 4의 누적 합은 0, 3, 4, 8이다. 인덱스 1부터 3 직전까지의 합은 8−3=5로 계산한다.
주의할 점
원소가 바뀌면 이후 누적 값도 영향을 받는다. 잦은 갱신과 질의가 함께 필요하면 펜윅 트리나 세그먼트 트리를 검토한다. 합의 정수 오버플로도 주의한다.