구간 합

 

[구간 합]

구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.

 

[구간 합의 핵심 이론] 

구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다. 

배열 A 가 있을 때 합 배열 S는 아래와 같이 정의한다. 

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

 

 이게 무슨 말이냐 하면, 

배열의 0번째 인덱스부터 마지막 인덱스까지의 모든 숫자를 하나씩 합쳐 가며 배열을 만드는 것이다.  

[합배열을 만드는 공식]

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

 

 

[구간 합을 구하는 공식] 

S[j] = S[i -1]; 
//j에는 마지막 배열의 값 i 는  시작 인덱스 번호

 

예를 들면 이렇게 구하고자 하는 마지막 인덱스(j) - 시작 인덱스 (i) 를 하면 결과 값이 나온다.