[알고리즘] 구간 합

구간 합(prefix sum)

배열이나 리스트에서 특정 구간의 합. 1차원 리스트에서 i 인덱스 부터 j 인덱스 까지의 합을 구하는 데 사용.

구간 합 알고리즘을 활용하려면 누적 합 배열을 알아야한다.

 

합 배열

만약 배열의 0부터 N까지의 합을 구한다면 시간 복잡도는 O(N)이다.

 

합 배열을 사용하면 O(1) 안에 해결할 수 있다.

 

S[3] = A[0] + A[1] + A[2] + A[3]

S[i] = A[0] + A[1] + A[2] + ... + A[i - 1] + A[i]

 

배열:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

위 배열의 S[5]를 구하면 1 + 2 + 3 + 4 + 5 + 6 = 21

배열의 합을 구하는 시간 복잡도는 O(N)이다.

만약 합을 반복하여 구해야한다면 O(N^2) 이상이 되는 경우가 생긴다.

 

누적 합 배열을 구하는 것도 O(N)의 시간 복잡도를 가진다.

하지만 누적합을 구해놓았기 때문에 부분 합을 구할 때는 O(1)의 시간 복잡도를 가진다.

 

합 배열 공식:

S[i] = S[i - 1] + A[i]

 

구간 합 공식:

S[j] - S[i - 1]

i에서 j까지의 구간 합