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

구간 합 이란?

구간 합은 합배열을 이용하여 특정 구간까지의 합을 구하는 알고리즘(시간 복잡도를 더 줄이기 위함)

 

합배열 공식

▶  s[ i ] = s[ i - 1 ] + A[ i ] 

 

구간 합 공식

합배열을 먼저 구해놓고, 공식 적용

▶  s[ j ] - s[ i - 1 ] 

[예제]

A[2] ~ A[5] 까지의 합을 구하세요.

① 위의 합배열에서 공식을 대입

② 답  → S[5] - S[1] = 45

③ 풀이  

     → S[5]가 의미하는 것은? → A[0] ~ A[5] 의 합

     → S[1]가 의미하는 것은? → A[0] ~ A[1] 의 합