머지 소트 트리 (Merge Sort Tree)

Overview & Definition 머지 소트 트리는 백준 알고리즘 문제 13544 수열과 쿼리3 문제를 해결하기 위해서 사용하였던 자료구조입니다. 세그먼트 트리를 변형하여 만든 구조이기 때문에 초기화 하는 방법과, 쿼리 날리는 방법 등이 세그먼트 트리와 상당히 유사합니다. 세그먼트 트리는 리프 노드(Leaf Node)에 각 배열의 원소를 집어넣고, 부모노드에 자식 노드들의 최댓값이나 최솟값, 혹은 부분합을 저장해서 특정 구간에 대한 질의(Query)를 빠르게 처리하는데 특화된 자료구조입니다. 머지 소트 트리는 부모 노드에 각 자식 노드를 머지한 결과값을 저장한 배열을 저장합니다. 예를 들어서 왼쪽 자식 노드가 [1, 3, 5], 오른쪽 자식 노드가 [2, 4, 6]인 상태라면, 부모 노드는 [1, ..

2020.06.21