알고리즘

Prefix sum ( 누적합 ) 목적 : 범위가 아무리 넓어도 범위 안의 값들의 합(구간합)을 빠르고 간편하게 구하기 사용 이유 : 누적합을 만들고 구간합을 구하는 시간복잡도는 O(N)[누적합 배열을 만들때 걸리는 시간]*O(1) = O(N)이다. 일반적인 반복문을 사용해서 구간합을 구하려 하면 시간 복잡도가 O(n²)가 되버린다. 숫자가 커지면 간단한 코드를 돌리는데 시간이 한 세월이기 때문에 구간합을 구할때는 누적합을 사용하는게 좋아보인다. 누적합을 이용해 구간합을 구하는 예시 (그림으로 더 자세히 설명) = 2~5합 = psum[5]-psum[1] 누적합 배열을 만들기 편하려면 , 기존 배열의 0번째 인덱스는 비워두는 것이 좋다.왜냐하면 구현하면서 앞의 인덱스를 사용하기 때문이다. 아래 코드와 그..