구간 합이란?`구간 합(Prefix Sum)`은 배열에서 특정 구간의 합을 효율적으로 계산하기 위해 사용하는 알고리즘이다.구간 합의 핵심 이론구간 합 알고리즘을 사용하기 위해서는 먼저 `합 배열`을 구해야 한다. 배열 A가 있을 때 합 배열 S는 다음과 같이 정의한다.합 배열 S 정의S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] //A[0]부터 A[i]까지의 합  합 배열은 기존의 배열을 전처리한 배열이라 생각하면 된다. 합 배열을 미리 구해놓으면, 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 `O(N)`에서 `O(1)`로 감소한다. 합 배열은 어떻게 만들까?합 배열 S를 만드는 공식S[i] = S[i-1] + A[i] 이렇게 구현된 합 배열을 이용하면 구간..