[알고리즘] 구간 합

구간 합

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

 

1. 누적합(Prefix Sum)

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

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

• S[0]은 아무것도 더해지지 않은 상태이다. 즉, 0이다. (이렇게 하는 이유는 헷갈림을 방지하기 위해서이다.)

 

 

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]의 합 

• arr[1] + arr[2] + arr[3] = 2 + 3 + 1 = 6
• S[4] - S[1] = 11 - 5 = 6

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