구간 합(알고리즘)

구간 합이란? 연속된 숫자들의 배열에서, 원하는 구간까지의 합을 알고자 할 때 이용하는 알고리즘. ex) 1 ~ 10이 배열에 저장되어있다고 할 때, 합 배열은 1 3 6 10 ..과 같은 방식 합 배열에서의 1 = 1 / 3 = 1+2 / 6 = 1+2+3 / 10 = 1+2+3+4 if) 난 3 ~ 6의 합에 대해 알고 싶은데 어떻게 해야하나요? answer) 1 ~ 6의 합에서 1 ~ 2의 합을 뺀다면, 원하는 답을 얻울 수 있어요! 공식 합 배열 S의 정의 S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] (A[0]부터 A[i]까지의 합) 합 배열 S를 만드는 공식 S[i] = S[i-1] + A[i] (더하고자 하는 A[i]를, 이전까지의 합S[i-1]의 합)..

원문링크 : 구간 합(알고리즘)