Day-2 구간 합

---

1. 구간 합 이론

 

합 배열 S는 기존의 배열 A가 있을 때, 일정 범위의 합을 구해둔 배열이다.

미리 합 배열을 구해두면 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다.

 

합 배열이 없는 경우에는 배열 A를 순회해야 구할 수 있으므로 최악의 경우 0부터 n까지 돌게 된다.

따라서 이 경우 O(N)이 된다.

---

2. 구간 합 공식

• 합 배열을 만드는 공식 : S[i] = S[i-1] + A[i]
• 구간 합을 구하는 공식 : S[j] - S[i-1] (i에서 j까지의 합)

합 배열이 있는 경우에는 시간 복잡도가 O(1)이 된다.

이는 구간 합을 구할 때 특정 인덱스의 값을 참조해야 하는데 이 시간 복잡도가 O(1)이기 때문이다.

 

위 공식들을 이용하여 합 배열을 만들고 구간 합을 구하면 시간 복잡도를 줄일 수 있다.

---

3. 예제 문제

[11659] 구간 합 구하기 4 (JAVA)

[11660] 구간 합 구하기 5 (JAVA)