구간 합 알고리즘 (Prefix Sum Algorithm)
| 0번째 | 1번째 | 2번째 | 3번째 | 4번째 | 5번째 | 6번째 | 7번째 |
|---|---|---|---|---|---|---|---|
| 16 | -5 | -11 | -15 | 10 | 5 | 4 | -4 |
| 16 | 11 | 0 | -15 | -5 | 0 | 4 | 0 |
구간 합 알고리즘은 누적합 데이터를 통해서 구간합을 O(1)의 속도로 구할 수 있는 알고리즘이다.
첫번째 행은 데이터이고, 아래 행은 누적합 데이터이다.
예를 들어,
1번째 원소부터 5번째 원소까지의 구간 합을 구해야 한다면
위의 예시의 경우
arr[1]+arr[2]+arr[3]+arr[4]+arr[5] = (-5) + (-11) + (-15) + 10 + 5 = -16이다.
총 + 연산이 4번 사용되었다.
구간합 알고리즘을 사용하면
sum[5]-sum[0] = -16 으로 단 한번의 연산으로 구간합을 구할 수 있다.
정리하면,
a~b 까지 부분합을 구할 때,
sum[b] - sum[a-1]로 구할 수 있다.