구간 합

구간 합

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

 

핵심 이론

구간 합 알고리즘을 활요하려면 먼저 합 배열 S을 구해야 함

// 합 배열 S 정의
S[i] = A[0] + A[1] + A[2] + ... + A[i] // A[0]부터 A[i]까지의 합

 

// 합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i]

 

// 구간 합을 구하는 공식
S[j] - S[i-1] // i에서 j까지 구간 합