[PS] 백준 10999- 구간 합 구하기 2

📌 알고리즘 분류

---

해당 문제는 세그먼트 트리 알고리즘에 대한 이해가 필요한 문제입니다.
해당 문제는 Lazy propagation 알고리즘에 대한 이해가 필요한 문제입니다 - 추가예정
세그먼트 트리

📖 문제

---

백준 10999

💻 코드

---

세그먼트 트리를 이용하여, 구간의 합을 구하는 문제입니다. 중간의 수의 변경이 빈번히 일어나고, 수의 변경이 특정 index에서 일어나는 것이 아니라 구간에서 발생합니다. 따라서 기존 세그먼트 트리 알고리즘으로 문제를 풀게 되면 M번 발생하므로 O(MNlogN)의 시간복잡도가 발생하게 됩니다. 따라서 평범한 세그먼트 트리 알고리즘으로는 문제를 풀 수 없습니다. 느리게 갱신되는 세그먼트 알고리즘을 적용하여 문제를 풀어야 합니다.
알고리즘에 대한 설명은 별도의 글로 대체하겠습니다. 😎

📌 마무리

---

처음 푸는 등급의 문제 🔥🔥