[알고리즘 개념] 구간 합

구간 합의 핵심이론

구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야한다.
배열 A가 있을 때 합 배열 S는 다음과 같이 정의한다.
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A [i]

합 배열 S를 만드는 공식

S[i] = S[i-1] +A[i]

구간 합을 구하는 공식

S[j] - S[i-1]