[알고리즘] 구간 합 알고리즘(Prefix Sum)

구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야한다.

 

🟡 합 배열 정의

S[i]는 A[0]부터 A[i]까지의 합

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

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

 

합 배열을 미리 정의해 놓으면 일정 구간의 합을 구하는 것의 시간복잡도를 줄여준다.

+) 합 배열 없이 일정 구간의 합을 구하는것은 시간 복잡도가 O(N)이고,

합 배열이 있으면 시간 복잡도가 O(1)이다.

 

🟡 구간 합 공식

i부터 j까지의 구간 합은

S[j] - S[i - 1]