구간 합
배열 A
구간 합 배열 S
합 배열 공식 :
S[i] = S[i-1] + A[i]S[i] = A[0] + A[1] + … + A[i-1] + A[i]
i부터 j까지 구간 합 공식 :
S[j] - S[i-1]S[j] = A[0] + A[1] + A[2] + … + A[i-1] + A[i] + A[i+1] + … A[j]
S[i-1] = A[0] + A[1] + A[2] + … + A[i-1]
S[j] - S[i-1] = A[i] + A[i+1] + … A[j]
728x90
반응형