알고리즘 썸네일형 리스트형 [알고리즘] 구간 합 구간 합특정 구간의 합을 빠르게 계산하기 위한 알고리즘이다. 대표적으로 누적합 (Prefix Sum)을 이용하는 방식입니다. 1. 누적합(Prefix Sum)배열 A가 주어졌을 때, `A[i]부터 A[j]`까지의 합을 자주 구해야 한다면, 누적합 배열 S를 먼저 구해놓고 이를 이용해 빠르게 구간합을 계산할 수 있습니다.S[i] = A[0] + A[1] + ... + A[i-1] (1 ≤ i S[0]은 아무것도 더해지지 않은 상태이다. 즉, 0이다. (이렇게 하는 이유는 헷갈림을 방지하기 위해서이다.) 2. 구간 합 구하기`A[i]부터 A[j]`까지의 구간 합은 다음과 같이 누적합을 이용하여, 계산할 수 있습니다.i부터 j까지의 구간 합 = S[j+1] - S[i] 예시 : 0부터 2까지의 구간 합 (.. 더보기 이전 1 다음
