💡합 배열
구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다.
합 배열은 보통 S로 표현한다.
- A[0]부터 A[i]까지의 합
S[i] = A[0] + A[1] + A[2] ... + A[i-1] + A[i]
합 배열 공식
S[i] = S[i-1] + A[i]
💡구간 합
구간 합은 합 배열을 이용하여 시간복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.
A라는 배열이 있을 때 그 안에서 특정 범위의 모든 값들의 합을 구하고 싶을 때 이 값을 빨리 구할 수 있게 해준다.
구간 합 공식
합 배열을 사용해서 구간 합을 구할 수 있다.
i에서j까지의 구간합을 구하는 공식
S[j] - S[i-1]
💡만약 배열이 자주 바뀔 경우
만약에 배열의 값이 자주 바뀌면 세그먼트 트리, 인덱스 트리를 사용하면 된다.
이에 대한 내용은 뒷부분 강의에서 설명한다고 한다.
