1. 구간 합
- 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘
- 합 배열 : 기존의 배열을 전처리한 배열
- 합 배열을 사용하면 시간 복잡도를 O(N)에서 O(1)로 줄일 수 있다.
- 합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i]
- 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];
