구간합 은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.
즉, 기존 리스트의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소하며 이를 통해 시간복잡도를 줄일 수 있는것!
합배열 S를 만드는 공식 : S[i] = S[i-1] + A[i]
구간 합을 구하는 공식 (i에서 j까지 구간합) : S[j] - S[i-1]
프론트엔드 개발을 하고 있는 김태윤입니다.
https://www.cllaude99.com 에서 글을 작성하고 있습니다.