구간 합

구간 합 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 구간 합의 핵심 이론 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 함 합 배열 S 정의 S[i] = A[0] + A[1] + A[2] + … + A[i-1] + A[i] # S[i]는 A[0]부터 A[i]까지의 합 인덱스 0 1 2 3 4 5 배열 A 15 13 10 7 3 12 합 배열 S 15 28 38 45 48 60 합 배열 S를 만드는 공식 S[i] = S[i-1] + A[i] i에서 j까지 구간 합을 구하는 공식 S[j] - S[i-1] ex) A[2]부터 A[5]까지의 합 = A[0]부터 A[5]까지의 합 - A[0]부터 A[1]까지의 합 = S[5] - S[1] [문제 003] 구간 합 구하..