구간 합

💡 구간 합

• 수들의 나열에서 특정 구간의 합을 의미한다.
• 보통 배열에서 i ~ j 인덱스 사이의 값들의 합을 구하는데 사용한다.
• 반복문을 사용하여 i ~ j 사이의 값을더하는 알고리즘의 시간복잡도는 O(n)이다.
• 구간 합 알고리즘을 사용하여 구간 합을 구하는 경우 O(1)의 성능을 갖는다.

합 배열 이용

• S[i] = A[0] + A[1] + … + A[i - 1] + A [i]
• 합 배열 S를 만드는 공식 : S[i] = S[i - 1] + A[i]
• i ~ j 구간 합을 구하는 공식 : S[j] - S[i - 1]

index	0	1	2	3	4	5
기존 배열 A	15	13	10	7	3	12
합 배열 S	15	28	38	45	48	60

ex) A[2] ~ A[4]의 구간 합 구하기

• A[0] 부터 A[4] 까지의 합 = S[4]
• A[0] 부터 A[1] 까지의 합 = S[1]
• S[4] - S[1] = 20