알고리즘 03-2 구간 합

합 배열 S 정의

S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합

• 합배열 = 기존의 배열을 전처리한 배열
• 합 배열 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간복잡도가 O(N) -> O(1) 감소
  • 배열 A : 15 13 10 7 3 12
  • 합 배열 S : 15 28 38 45 48 60

합 배열 S를 만드는 공식

S[i] = S[i-1] + A[i]

구간 합을 구하는 공식

s[j] - s[i-1] // i에서 j까지 구간 합

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]