• 구간 합

//합 배열 정의
S[i] = A[0] + A[1] + A[2]+...+A[i-1] + A[i] //A[0]부터A[i]까지의 합

인덱스    0     1     2      3      4      5 
배열A    15    13    10      7      3      12
합배열S  15    28    38      45     48     60

//합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i]

//구간 합을 구하는 공식
S[j] - S[i-1] //i에서 j까지 구간 합

//A[2] ~ A[5] 구간 합을 합 배열로 구하는 과정
S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]
S[1] = A[0] + A[1]
S[5] - S[1] =  A[2] + A[3] + A[4] + A[5]

• 이렇게 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소합니다.

• 투포인터

• 백준11659문제 구간 합 구하기

• 백준11660문제 구간 합 구하기 5

• 백준2018문제 연속된 자연수의 합 구하기

• 백준1940문제 주몽

• 백준12891문제 DNA비밀번호