세그먼트 트리1

• 

  [c++] 백준-10999 구간합구하기2 (세그먼트트리, lazy_loading) 1. 문제 2. 입출력 및 예제 3. 문제 해설 이 문제는 백준 2042 구간합구하기 문제와 거의 동일하다. 단 하나 차이점이 있다면 이 문제에서는 단 하나의 수를 교체하는 것이 아니라 2번째 수부터 8번째 수를 9로 변경해 등과 같이 구간이 업데이트 된다는 점이다. 이 경우 최악의 시간복잡도는 처음부터 끝 구간을 변경하는 경우가 되고 update하는 데 드는 시간이 O(NlogN)이 된다. 이 문제에서 N은 백만이고 O(NlogN) 은 백만 * 1000 = 10억 번의 연산을 해야한다는 것이다. 대략적으로 c++언어로 1초라는 제한시간안에 통과하려면 1억번 정도의 연산을 수행해야하는데 위의 연산 횟수는 터무니 없다고 할 수 있다. 따라서 이 문제는 일반적인 세그먼트 트리의 update를 적용해서는 안된.. c++/알고리즘 2023. 2. 15.