- 알고리즘/개인공부
[자료구조] 구간 합
더모어더베러
2024. 6. 17. 23:06
구간합은 합배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 입니다.
구간합을 사용하기 위해서 합배열을 구해야 하는데 합배열을 구하는 방식은 아래와 같습니다.
합 배열 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]까지의 합을 구할수가 있습니다.
출처