코딩 헬스장

( 누적합 알고리즘 간단 예제 ) [ 1, 2, 3, 4, 5 ] 로 이루어준 숫자 배열에서 각 구간까지의 합을 구하는 배열 [ 1, 3, 6, 10, 15] 을 구한다고 가정해보면 아래와 같이 2가지로 구할 수 있습니다. [ 첫번째 방법 ] 1 1+2 1+2+3 1+2+3+4 1+2+3+4+5 식으로 각 인덱스까지의 값을 반복하며 구하기. [ 두번째 방법 ] 1 1+2 3+3 6+4 10+5 식으로 이전 인덱스까지의 누적합에 현재 인덱스의 값을 더하여 구하기. 2가지 방법을 비교해보면 두 번째 방법이 훨씬 효율적이라는 것을 알 수 있습니다. 누적 합 이란 수열 An에 대해서 각 인덱스까지의 구간의 합을 구하는 것을 누적 합이라고 합니다. 시작점은 항상 첫번째 원소이며, R번째 원소까지의 합을 앞에서부터..