구간 합
합 배열을 이용하여 시간복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘
•
구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야한다.
•
합 배열은 기존의 배열을 전처리한 배열과 같다.
•
이렇게 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간복잡도가
•
O(N)에서 O(1)로 감소한다.
합 배열 S를 만드는 공식은 아래와 같다.
구간 합을 구하는 공식은 아래와 같다. (i에서 j까지 구간 합)
배열 A의 A[2]부터 A[5]까지의 구간 합을 합 배열을 통해 구하는 과정
•
위 구간 합을 구하는 공식을 이용하면 S[5] - S[1]이 된다.
