구간합 배열(Prefix Sum)

구간합 배열이란

 

만약 N개의 값으로 이루어진 배열이 주어졌을 때, 부분 배열의 합을 구하려면 반복문을 돌리면 

 

O(N)이 걸리지만, 구간합 배열을 사용하면 O(1)에 구할 수 있다.

 

구간합 배열 설명

 

출처 https://osgoodgunawan.medium.com/prefix-sum-80d531154b95

 

 

Sum 배열은 N 또는 N+1로 이루어진 배열이다.

 

위의 그림은 N으로 되어있다.

 

P[0]은 A[0]과 같다.

 

그 다음 P[1]은 P[0] + A[1]

 

P[2]는 P[1] + A[2]

 

P[3]은 P[2] + A[3]

 

으로 구할 수 있다.

 

이처럼 반복문을 사용한다면, 하나씩 더해야 할 것을

 

구간합 배열을 사용하면 O(1)에 구할 수 있다.

 

만약 A[1] + A[2]를 구하고 싶다면 어떻게 하면 될까?

 

P[2] - P[0] 이 된다.

 

P[2] - P[0] =  (A[0] +  A[1] + A[2]) - A[0] 

 

이기 때문이다.