구간 합이란 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 알고리즘이다.
구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다.
합 배열 S 정의
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]합 배열 = 기존의 배열을 전처리한 배열
합 배열을 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간복잡도가
O(N)에서 O(1)로 감소
합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i]구간 합을 구하는 공식
S[j] - S[i-1]A[2] ~ A[5] 구간 합을 합 배열로 구하는 과정
S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]
S[1] = A[0] + A[1]
S[5] - S[1] = A[2] + A[3] + A[4] + A[5]
웹!