[알고리즘] 구간 합

특정 구간의 합을 빠르게 계산하기 위한 알고리즘이다. 대표적으로 누적합 (Prefix Sum)을 이용하는 방식입니다.

1. 누적합(Prefix Sum)

배열 A가 주어졌을 때, `A[i]부터 A[j]`까지의 합을 자주 구해야 한다면, 누적합 배열 S를 먼저 구해놓고 이를 이용해 빠르게 구간합을 계산할 수 있습니다.

S[i] = A[0] + A[1] + ... + A[i-1]  (1 ≤ i < N)

2. 구간 합 구하기

`A[i]부터 A[j]`까지의 구간 합은 다음과 같이 누적합을 이용하여, 계산할 수 있습니다.

i부터 j까지의 구간 합 = S[j+1] - S[i]

예시 : 0부터 2까지의 구간 합 (S[3] - S[0])

S[3] = A[0] + A[1] + A[2]

S[0] = 0

3. 사용 예제

기본 배열 (arr)

arr = [ 5, 2, 3, 1, 7 ]   // index 0  1  2  3  4

누적합 배열 (prefix sum)

S = [ 0,   5,   7,  10,  11,  18 ]   // S : 누적합 , index 0   1   2   3   4   5
      |    |    |    |    |    |
      0   0+5 0+5+2 ...    전체합

즉, S[i]는 arr[0]부터 arr[i-1]까지의 합입니다.

S의 크기는 arr보다 한 칸 더 크다.(아무것도 더해지지 않는 경우, 0을 포함)

구간 합 구하기

sum = S[j + 1] - S[i];

예시 : 구간 [1, 3]의 합

❗구간 [1, 3]의 의미는 arr 배열의 1번부터 3번 인덱스까지의 구간 합을 의미한다. (인덱스와 순서가 헷갈리지 않게 조심)

kimyongjun0129