구간 합: 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘
합 배열 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]
구간 합을 구하는 공식
- S[j] - S[i - 1]
- i에서 j까지의 구간 합