알고리즘

Prefix sum ( 누적합 )장점 : 한번 누적합 배열을 만들어 놓으면 구간합을 빠르게 구할 수 있다.구간합 : 배열에서 특정 구간의 합 ( 예시 : arr[1234] ~ arr[1000000]까지의 모든 원소들의 합 )속도차이 ( 시간복잡도 )반복문을 사용해서 구간합을 연속적으로 구하는 일반적인 경우 시간복잡도는O(n)(반복문) x O(n)(구간합계산) = O(n²)이다. 하지만 누적합을 사용한다면O(n)(누적합 배열 구현) + O(n)(반복문) x O(1)(구간합 계산) = O(n)이 된다. 즉 훨씬 빠르다는 소리다.구현예시 누적합 구현시, 현재 위치 직전의 인덱스를 사용하기 때문에 기존 배열의 0번째 인덱스는 비워두는 편이 구현하기 수월하다.아래 코드와 그림을 보면 더 쉽게 이해할 수 있다.//..