구간합
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] : A[0]부터 A[i]까지의 합
- 미리 합 배열을 구해놓으면 기존 배열의 일정범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다.
- 합배열을 만드는 공식 : S[i] = s[i-1] + A[i]
[예제]
A : 3, 6, 5, 10, 4
S : 3, 9, 14, 24, 28
- 구간합을 구하는 공식 : S[j] - S[i-1], i부터 j까지 구간 합
[예제]
S[5] : A[0]~A[5] 만큼 더한 값
S[1] : A[0]~A[1] 만큼 더한 값
인덱스 2부터 인덱스 5까지 더한 값은 S[5]-S[1]과 같다.
