구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘
구간 합의 핵심 이론
구간 합의 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다.
합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i] 구간 합을 구하는 공식(i에서 j까지 구간 합)
S[j] - S[i-1]구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘
구간 합의 핵심 이론
구간 합의 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다.
합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i] 구간 합을 구하는 공식(i에서 j까지 구간 합)
S[j] - S[i-1]