lazy propagation(16975 수열과 쿼리 21)

16975번: 수열과 쿼리 21

1.접근

N은 십만 M도 십만이다. N^2으로 해결 불가능하고 NlogN으로 해결한다고 생각했다.

구간 합을 구하는 문제가 아닌 구간에 k를 더하는 문제이다. 생각을 조금 바꿔보자.

세그먼트 트리와 관련되서 생각해보니 1번 쿼리가 들어왔을 때 각 리프노드에 k를 더하지 않고

구간에 해당되는 노드에 k를 넣어놓고 출력할때 꺼내가면 된다고 생각했다.

2.풀이

우선 하던대로 완전 이진 트리를 리프노드만 전처리한다.

리프위에 노드들은 구간합같은 문제가 아니라서 저장되어있을 필요가 없다.

1번 쿼리가 들어올 때는 구간을 나눠서 구간에 해당되는 모든 노드에 k를 더해준다.

그 후 2번 쿼리가 들어올 때 리프노드를 바로 출력하지 않고 1번 쿼리에 따라 변경되어있을 값들이

중간 노드들에 저장되있을 것이므로 리프부터 루트까지 타고 올라가면서 모두 더해준 값을 출력한다

이렇게되면 O(nlogn)에 문제를 풀 수 있다.

 

3.코드

4.배운점

• 문제를 풀어보고 분류에 느리게 갱신되는 세그먼트 트리가 뭔지 궁금해서 찾아봤더니 내가 푼 방법이 lazy propagation 이라고 부르는 방법이였다.