Segment Tree with Lazy Propagation (1) 썸네일형 리스트형 162. Segment Tree with Lazy Propagation 다음과 같은 쿼리를 처리하는 문제를 생각해 보자. $1\ x\ y\ k$: $x$번째 수부터 $y$번째 수까지에 $k$를 더한다. $2\ x\ y$: $x$번째 수부터 $y$번째 수까지의 합을 출력한다. 만약 세그먼트 트리를 이용해서 이 쿼리를 처리하려고 한다면 $1$번 쿼리를 처리할 때 원소의 값을 바꾸는 작업을 $y - x + 1$번 실행해야 하고, 수의 개수가 $n$이라면 이 작업에는 $(y - x + 1) \lg n$만큼의 시간이 걸린다. 즉 이 시간은 바꿔야 하는 구간의 크기에 영향을 받는다. 만약 $x = 1, y = n$이라면 $1$번 쿼리 하나를 처리하는 데 $n \lg n$만큼의 시간이 걸릴 것이고 이런 쿼리가 $m$개 있다면 $nm \lg n$만큼의 시간이 걸리게 된다. 이런 시간복잡도.. 이전 1 다음
