어떤 트리가 주어져 있을 때, 루트에서 시작하여 모든 노드를 DFS로 방문하면서, 방문한 순서를 각 노드의 번호로 부여하면, 모든 노드에 대해 그 노드의 서브트리에 있는 노드는 연속된 구간의 번호를 갖게 됩니다.
따라서, 어떤 트리에서 노드의 서브트리에 대한 업데이트 쿼리를 진행하고자 할 때, DFS 방문순서를 활용하면 서브트리 쿼리를 O(logN)에 진행할 수 있습니다.
이를 오일러 투어 테크닉이라고 부릅니다. 자세한 방법은 검색해보시기 바랍니다.
chickenchickenlove 2년 전
안녕하세요, 문제를 푸는데 어려움이 많아 조언을 구하고자 글을 작성합니다.
저는 노드를 구성(Lazy, 자식노드, 현재 값)을 하고, 칭찬 계수 업데이트시에는 바로 인덱스로 접근해서 O(1)을 구현하였습니다.
다만, Query를 하는 과정에서는 앞서 칭찬 계수 업데이트시에 달아두었던 Lazy를 하나씩 업데이트하면서 내려가야해서... 최악의 경우 한번 Query를 진행하는데 O(N)의 시간복잡도가 발생합니다. M개의 Query가 들어오면 O(NM)이 되어 시간초과가 발생하는 것으로 예상되는데요... 혹시 이런 부분을 해결할 수 있는 방법이 없을까요?
아래에 코드 첨부 드립니다.
항상 도움 주셔서 감사합니다.