합배열

[TIL] 알고리즘 구간 합

✍ Today I Learned 구간 합 구간 합이란? 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 합 배열 구하기 // 배열 A가 있을 때 합 배열 S의 정의 S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합 // 합 배열을 만드는 공식 S[i] = S[i-1] + A[i] 이렇게 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소 구간 합 구하기 // 구간 합 구하는 공식 S[j] - S[i-1] // i에서 j까지 구간 합 // A[2] ~ A[5] 구간 합을 합 배열로 구하는 과정 S[5] = A[0] + A[1] + A[2] + A[..