[자료구조] 구간 합

구간합은 합배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 입니다.

 

 

구간합을 사용하기 위해서 합배열을 구해야 하는데 합배열을 구하는 방식은 아래와 같습니다.

 

합 배열 S를 만드는 공식

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

 

 

 

 

 

구간 합을 구하는 공식

i 에서 j 까지의 구간합 = S[ j ] - S[ i-1 ]         // 위의 그림의 경우 2(i)에서 5(j)까지의 구간합

 

합배열을 미리 구해놨다면 위의 공식을 사용하여 구간합을 구할수 있는데 

위의 그림 경우 S[5] - S[1] 을 하면 A[2] ~ A[5]까지의 합을 구할수가 있습니다.

 

 

 

---

출처 

https://www.inflearn.com/course/lecture?courseSlug=%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%90%EB%B0%94&unitId=148269&tab=curriculum