Processing math: 100%

본문 바로가기

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$ 만큼의 시간이 걸리게 된다. 이런 시간복잡도로는..

티스토리툴바