구간 합

합 배열(S)을 구하는 것부터 시작한다.

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

인덱스	0	1	2	3	4	5
리스트 A	3	5	2	1	9	6
합 배열 S	3	8	10	11	20	26

ex) S[4] = A[0] + A[1] + A[2] + A[3] + A[4] = 3 + 5 + 2 + 1 + 9 = 20

 

A[i] ~ A[j] 리스트의 합을 구한다고 하자.

- 합 배열(S) 없이 구한다면, 최악의 경우 시간 복잡도가 O(N)이다.

- 하지만 위의 합 배열을 사용한다면 O(1)으로 시간 복잡도가 확 줄어든다.

 

합 배열 S 구하는 공식

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

 

구간 합 구하는 공식(A[i] ~ A[j] 리스트의 합)

S[j] - S[i-1]

 

예를 들어서 A[1] ~ A[4] 구간을 구한다고 해보자.

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

S[0] = A[0]

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