MathTrauma

문제 링크 : https://www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net Lazy Propagation 연습 문제인가? 더 효율적인 방법이 있을 것 같은데... 여기 있는 코드는 흔히 사용되는 코드들과 약간 다를 것인데, 관련된 설명은 다음 글에 있다. 2022.09.04 - [BOJ/Segment Tree] - BOJ 10999 구간합 구하기 2 - 두 가지 구현 BOJ 10999 구간합 구하기 2 - 두 가지 구..

Range update 를 해야 하기 때문에 소위 Lazy Propagation 을 구현해야 하는데... 두 가지 다른 구현을 가지고 비교해 보기 위해 글을 쓴다. 두 구현의 우열을 논하는 것은 아니다. 이해하기 편한 쪽을 선택하면 되겠다. 구간 업데이트가 \( O(\log(n))\) 으로 동작하려면 어떻게 되어야 하는가? (1) node 의 관리 구간이 업데이트 구간에 포함되면 더 이상 하위 노드로 재귀 호출을 해서는 안된다. (2) 도달한 노드의 대표값은 업데이트 되어야만 한다.(그래야 상위 노드의 값도 제대로 된 값을 가지게 된다.) 위의 두 사항을 염두에 두고 있자. 1. 널리 쓰이는 구현 이제 흔히 보이는 lazy propagation 구현 코드부터 보자. 먼저 range update 를 수행하..