CodeAngie

배열의 일부 구간에 대한 합을 빠르게 구할 수 있는 알고리즘이다.배열의 값들이 변하지 않는다면 누적된 합 또한 변동이 없다는 점을 적용한다.미리 구해둔 누적합을 통해 배열 중 특정 구간의 부분합을 쉽게 구할 수 있다.값을 미리 저장해 두는 점이 DP와 유사하다.배열의 값들이 변하지 않음1. 1차원 누적합 알고리즘1.1. 1차원 누적합그림과 같이 앞에서부터 차례대로 누적된 합계를 prefixSum 배열에 저장한다.첫 번째(0) 값은 arr 값과 prefixSum 값이 동일하다.현재 위치(i)의 arr 값에 prefixSum 배열에 저장된 직전 위치(i-1)까지의 합을 더하여 현재 위치의 누적합을 구하여 prefixSum에 입력한다.점화식은 다음과 같다.prefixSum[i] = prefixSum[i-1] ..