구간 합

구간 합이란?

합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘

 

합 배열 S 정의

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

 

합 배열을 만드는 공식

S 배열은 합 배열, A 배열은 일반 배열을 뜻함

EX) 배열 A = {3, 6, 5, 10, 4}

       배열 S = {3, 9, 14, 24, 28}

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

 

구간 합을 빠르게 구하는 공식

S는 합 배열임

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