누적합 알고리즘의 정의 누적합 알고리즘은 말 그대로 어떠한 구간의 누적된 합을 구하는 알고리즘이다. 수열 \(A_n\)에 대하여 특정 인덱스 a에서 b까지의 구간 합을 구하는 알고리즘이라고도 볼 수 있다. 예시 [ 1,2,3,4,5 ] 로 이루어진 크기가 5인 배열 arr가 있다. 이 때 arr[1] 부터 arr[3]의 구간 합을 구해보자. (방법 1) 가장 쉬운 방법으로, 2부터 4까지 인덱스를 하나씩 증가시키며 배열을 방문하여 요소들을 더한다. 1 1+2 1+2+3 = 6 만일 배열의 처음부터 해당 인덱스까지의 합을 나타내는 배열 [ 1,2,6,10,15 ]을 구하려고 하면 어떨까? 1 1+2 1+2+3 1+2+3+4 1+2+3+4+5 위를 보면 알 수 있듯이, 0을 제외한 모든 인덱스에서 자신 이전..