구간 합이란?
`구간 합(Prefix Sum)`은 배열에서 특정 구간의 합을 효율적으로 계산하기 위해 사용하는 알고리즘이다.
구간 합의 핵심 이론
구간 합 알고리즘을 사용하기 위해서는 먼저 `합 배열`을 구해야 한다. 배열 A가 있을 때 합 배열 S는 다음과 같이 정의한다.
합 배열 S 정의
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] //A[0]부터 A[i]까지의 합
합 배열은 기존의 배열을 전처리한 배열이라 생각하면 된다.
합 배열을 미리 구해놓으면, 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 `O(N)`에서 `O(1)`로 감소한다.
합 배열은 어떻게 만들까?
합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i]
이렇게 구현된 합 배열을 이용하면 구간 합도 쉽게 구할 수 있다.
i에서 j까지 구간 합을 구하는 공식은 다음과 같다.
구간 합을 구하는 공식
S[j] - S[i-1]
만약 위 예시에서, 2번째 index ~ 4번째 index까지의 구간 합을 구해야 된다면?
`S[4] - S[1]` 을 하면 12의 구간합이 나오게 된다.
합 배열과 구간 합 공식을 활용하면 코딩 테스트에서 시간 복잡도를 줄이는데 많은 도움이 된다.