원래는 segment tree에서 update를 할 때, 하나의 수에 대해서 update를 logN만에 할 수 있었는데, 이 문제에서는 구간을 update해야 한다. 즉 (구간의 길이)*logN의 시간이 걸리는 것이다.
Range update를 O(logN)만에 할 수 있는 방법이 있다.
segment tree + lazy propagation을 활용하는 것이다.
lazy propagation을 이용하면 범위에 포함되는 트리의 leaf node까지 다 업데이트를 해주지 않는다. 일단은 그 범위를 대표하는 node까지(node의 위에 있는 노드들도)만 업데이트 한다. 그리고 lazy라는 배열에 그 node의 자식 node들에 얼마나 업데이트 해줘야 하는지 기록해놓는다. 대충 여기까지 하면 일단 O(logN)만에 구간 업데이트가 된 것이다. 엥? 그렇다면 다른 쿼리가 들어오면 어쩌려고... 다음에 업데이트한 구간에 조금이라도 관련있는(걸쳐있는) 쿼리나 업데이트가 필요할 경우, 필요한 노드들의 lazy배열을 살펴본다. 그래서 lazy배열에 얼마나 업데이트 해줘야할지 있는 기록을 보고 그 노드를 업데이트 해주고, 그 lazy배열을 0으로 만든 후 자식 노드에게 전파해준다. 이렇게 필요한 경우 lazy배열을 살펴보고 업데이트 해줘서 필요한 노드의 값만 챙기고 그 자식노드의 업데이트는 다음으로 미루는 식이다.
물론 이렇게 하면 그냥 point update할 때보다 아주 조금 더 시간이 들긴하겠지만 O(logN)이다.
특이한 점은 쿼리를 할 때도 업데이트가 진행되는 것이다. 그리고 어떤 노드의 업데이트가 진행되면 그 노드 위의 노드들의 업데이트는 원래 재귀 업데이트 방식으로 되면 된다.
달라지는 것은 필요한 것까지만 취하고, 그 아래 자식들의 업데이트를 뒤로 미뤄놓고 필요할 때만 해주거나, 필요한 걸 찾으면서 어차피 지나가는 김에 해주고 가는 식이다.
그래서 O(logN)만에 가능한 것이다.
정말 멋있는, 대단한 방법이다. 이런 방법을 어떻게 생각해 냈을까...나도 완벽히 이해한 것은 아니기 때문에 좀 더 공부해보고 직접 짜봐야겠다. 그리고 아래에 적어놓은 두 사이트의 도움을 많이 받았다.
자동차 공장 문제를 풀 때 처럼, Fenwick Tree의 range update, range query를 이용해서도 풀 수 있을 것 같은데 일단 lazy propagation을 해본 후에 도전해 보고, 거꾸로 자동차 공장 문제도 segment tree+lazy propagation을 이용해서 풀어봐야겠다.
Segment Tree + Lazy Propagation 을 공부한 곳인데, 정말... 단계별 그림과 친절한 설명과 코드로 완벽에 가깝게 설명이 돼있다. 물론 그래도 내 실력에서느느 이해하는 게 쉽지는 않았다. 이것을 이해하려면 Segment Tree에 대해서도 잘 이해해야 하고, 아래의 자료를 오랜 시간 보면서 여러번 읽어보고 해야할 것이다.
댓글 없음:
댓글 쓰기