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

핵심 이론

합 배열 S 의 정의

// A[0]부터 A[i]까지의 합

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

합 배열은 기존의 배열을 전처리한 배열이라 생각하면 된다.
이렇게 합 배열을 미리 구해놓으면 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다.

합 배열 S 를 만드는 공식

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

이렇게 구현된 합 배열을 이용하여 구간 합 역시 쉽게 구할 수 있다.

구간 합을 구하는 공식

// i에서 j까지 구간 합

s[j] - S[i-1]

팁

배열의 0번째 인덱스로 인해 인덱스가 헷갈리는 경우가 많이 발생한다.
합 배열과 기존의 배열을 정의할 때 0번 인덱스 요소를 비워둔 채로 사용하지 않도록 하자.
이렇게 하기 위해서는 기존의 배열 크기보다 조금 더 크게 정의하는 것이 좋다.
배열의 크기는 4로 떨어지는 숫자로 정의하는 것을 추천한다.
예) 1000칸이 필요하다면 1004칸을 정의