[백준 13544 | 머지 소트 트리] 수열과 쿼리 3

풀이 세그먼트트리를 응요한 자료구조인 머지 소트 트리(Merge Sort Tree)를 이용하면 O((logn)^2)시간 안에 해결할 수 있는 문제입니다. 머지 소트트리는 간단하게 말해서 트리의 각 노드에 자식들의 최솟값이나 최댓값을 저장하는 것이 아니라, 머지소트(Merge Sort)시에 일어나는 각 배열들의 중간 상태를 저장하는 자료 구조입니다. [5, 2, 4, 6, 1, 3, 2, 6]의 배열을 머지소트를 이용해서 정렬할 경우, 위의 그림과 같은 과정을 거치게 됩니다. 이 때, 각 노드의 상위 노드에는 두 배열을 머지하여 생긴 새로운 배열을 저장합니다. 즉 배열(혹은 리스트)의 배열 구조를 띄게 되는 것입니다. 이렇게 머지소트트리를 생성하고 난 후에는 쿼리를 날려서, 각 구간안에 포함되는 배열들 중..

2020.06.21