merge sort tree

머지소트트리 (merge sort tree)머지 소트 트리는 세그먼트 트리의 변형으로, 특정 구간에서 정렬된 데이터를 효율적으로 처리할 수 있는 자료구조이다. 주로 구간 내 특정 값의 개수를 세거나 k번째 작은 수를 찾는 문제 등에 활용된다. 1. 머지 소트 트리의 개념머지 소트 트리는 세그먼트 트리와 비슷하지만, 각 노드에 구간에 해당하는 데이터를 정렬된 상태로 저장한다. 세그먼트 트리에서 각 노드가 단일 값을 저장하는 반면, 머지 소트 트리에서는 리스트 또는 배열 형태로 정렬된 값을 저장한다.2. 머지 소트 트리의 구성리프 노드: 각 배열의 원소를 저장내부 노드: 해당 구간의 두 하위 노드 데이터를 합친 후 정렬한 리스트를 저장3. 구현 방법1) 트리 구축void build(int s, int e, ..