구간 합

구간 합은 합 배열을 이용해 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘.
코딩테스트에서 사용 빈도가 높다!

구간 합의 핵심 이론

합 배열 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]