구간 합 ( 핵심이론 )

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

구간 합의 핵심 이론

구간 합 알고리즘을 활용하려면 먼저 합 배열 구하기

합 배열 S 정의

S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] //A[0]~A[i]까지의 합 

• 합 배열은 기존의 배열을 전처리한 배열
• 미리 구해놓으면 일정 범위의 합 구하는 시간 복잡도가 O(N) → O(1)

합 배열 S 만드는 공식

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

구간 합을 구하는 공식