[백준 10999번] 구간 합 구하기2

---

10999번: 구간 합 구하기 2

---

 

목차

• 사전 지식
• 문제 접근
• 문제 풀이

 

 

사전 지식

• 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크)
• 느리게 갱신되는 세그먼트 트리(Segment Tree with Lazy Propagation)를 알고 있으면 좋다 (링크)

 

 

 

문제 접근

백준 2042번 문제(링크)와 이번 문제의 차이점을 정확히 인지하는 것이 중요하다.

2042번 문제는 한 번에 한 개의 원소만 갱신되는 반면, 이번 문제는 한 번에 구간 단위로 갱신된다.

 

기본 세그먼트 트리 풀이

이번 문제를 기본 세그먼트 트리를 이용하여 풀면 어떻게 될까?

배열의 길이는 $N \leq 10^6 \ $이며, 쿼리(질의)의 개수는 각각 $M \leq 10^4, K \leq 10^4 \ $이다.

구간의 합을 구하는 쿼리는 $O(\log N)$의 시간이 걸리므로 별 문제가 안 된다.

하지만, 구간에 수를 더하는 쿼리는 $O(N \cdot \log N)$에 근사하는 시간이 걸린다.

그러므로, 최종 시간 복잡도는 $O(N + (MN + K) \cdot \log N)$이 나오므로 TLE(Time Limit Exceed) 오류가 발생한다.

 

따라서, 우리는 구간의 합을 구하는 쿼리를 더 효율적으로 처리하는 방법을 찾아야 한다.

 

 

 

문제 풀이

결론부터 말하면 이 문제는 느리게 갱신되는 세그먼트 트리(Segment Tree with Lazy Propagation)를 이용하여 풀 수 있다.

이를 이용하면 구간 단위로 업데이트하는 쿼리를 구간 쿼리와 비슷하게 처리할 수 있다.

즉, 구간에 수를 더하는 쿼리와 구간의 합을 구하는 쿼리를 모두 $O(\log N)$의 시간에 수행할 수 있다.

따라서, 최종 시간 복잡도는 $O(N + (M+K) \cdot \log N)$으로 문제를 해결할 수 있다.

 

느리게 갱신 되는 세그먼트 트리에 관한 자세한 설명은 여기를 참조하기 바란다.