누적합, 구간합 누적합과 구간합이란? 누적합은 배열의 각 원소까지의 합을 계산한 배열을 말합니다. 구간 합은 합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 알고리즘입니다 합 배열은 보통 S라고 표현합니다. 합 배열과 누적합은 개념적으로는 비슷하지만 합 배열은 누적합과 달리, 0부터 i까지의 합을 나타내는 것이 아니라 1부터 i까지의 합을 나타냅니다. 하지만 알고리즘을 푸는데 있어서는 두 개념을 혼용해서 사용하여도 크게 문제는 없을 것 같습니다. 배열 A가 있을 때 합 배열 S는 이렇게 표현합니다. S[i] = A[0] + A[1] + A[2] ......+..... A[i - 1] + A[ i ] 그러면 합배열을 사용하는 이유는 뭘까요? => 합 배열을 미리 구해놓게 되면 기존 배열의 일정 범위의 합을 구하는 .. 이전 1 다음