C++ - 구간합 이론

배열 A, 합 배열 S를 미리 구하면

시간 복잡도가 O(N)에서 O(1)로 감소된다.

 

인덱스	0	1	2	3	4	5
배열 A	15	13	10	7	3	12
합 배열 S	15	28	38	45	48	60

 

 

합 배열 S를 만드는 공식

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

 

 

구간 합을 구하는 공식

S[j] - S[i-1] // i에서 j까지 구간합

 

 

A[2] ~ A[5] 구간합을 구하는 공식

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

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