구간 합

구간 합은 합 배열을 이용하여 시간 복잡도를 줄이는 목적의 알고리즘이다.

구간, 범위, i부터 j까지, 연속된과 같은 단어들이 보인다면 구간 합을 떠올려 보자.

구간 합의 설명

배열의 인덱스 i부터 j까지의 합을 구하기 위해 반복문을 사용하면 O(n)의 시간 복잡도를 가진다.
하지만 합 배열을 이용하면 시간 복잡도를 O(1)로 개선시킬 수 있다.

합 배열

구간 합을 구하기 위해서는 합 배열을 먼저 구해야만 한다.
배열 A가 있을 때 합 배열 S는 다음과 같이 정의한다.

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

구간 합

배열의 인덱스 i부터 j까지의 합을 Sum[i, j]이라고 하자.
이때 Sum[i, j]는 아래와 같이 구할 수 있다.

Sum[i, j] = S[j] - S[i - 1]

구간 합의 예시

A[] = {10, 13, 43, 20, 50, 68} 인 집합 A가 있다고 하자.
이때 3번째부터 5번째 원소의 합을 구해보자.

A[]로부터 먼저 합 배열 S[]를 구한다.

A[] = {10, 13, 43, 20, 50, 68}
S[] = {10, 23, 66, 86, 136, 204}

합 배열 S[]를 이용하여 구간 합 Sum[3, 5]를 구한다.
그리고 실제로 맞는지 검산도 진행한다.

Sum[3, 5] = S[5] - S[2] = 136 - 23 = 113
A[3] + A[4] + A[5] = 43 + 20 + 50 = 113