머지 소트 트리 Merge Sort Tree

머지 소트 트리의 각 노드가 가지고 있는 원소들을 도식화 한 그림

머지 소트 트리는 세그먼트 트리의 파생형으로 위 그림처럼 각 node가 정렬된 구간을 보유하는 형태로 되어있다.

 

머지 소트 트리는 세그먼트 트리와 유사하게 구현할 수 있다.

초기화

void set_mst(int node, int start, int end)
{
    vector<int> &cur = mst[node];
    if (start == end)
    {
        cur.push_back(ar[start]);
        return;
    }

    int m = mid(start, end);
    set_mst(node * 2, start, m);
    set_mst(node * 2 + 1, m + 1, end);

    vector<int> &l = mst[node * 2], &r = mst[node * 2 + 1];

    cur.resize(l.size() + r.size());
    merge(l.begin(), l.end(), r.begin(), r.end(), cur.begin());
}

 

머지 소트 트리의 초기화는 std::merge가 이용된다.

 

먼저 리프 노드에 원소를 삽입한 후 부모에 두 자식 노드를 merge 한 결과를 넣는 것으로 각 노드가 정렬된 구간을 보유할 수 있게 된다.

 

각 노드가 구간을 담아야 하므로 공간 복잡도는 $O(NlogN)$이 된다. 구현의 편의성을 위해 세그먼트 트리를 구현할 때처럼 4 * N으로 크기를 잡아도 될 것이다.

질의 - 특정 구간에 있는 원소의 index 찾기

int query(int node, int start, int end, int l, int r, int x)
{
    if (l > end || r < start) return 0;
    if (l <= start && end <= r)
        return lower_bound(mst[node].begin(), mst[node].end(), x) - mst[node].begin();
    
    int m = mid(start, end);
    return query(node * 2, start, m, l, r, x) + query(node * 2 + 1, m + 1, end, l, r, x);
}

 

머지 소트 트리에서 기본적으로 이용하는 질의는 특정 구간에 있는 원소의 위치를 찾는 것이다.

 

코드에서 인자로 주어지는 x가 찾으려는 원소이다.

 

노드가 찾으려는 구간을 포함한다면 이진 탐색을 이용하여 찾은 index를 반환할 수 있다.

 

이 query 에서 이진 탐색과 관련된 부분은 문제가 어떤 걸 요구하느냐에 따라 그 구현이 달라질 수 있으므로 적절한 판단이 필요할 것이다.

 

query 함수의 시간 복잡도는 원하는 구간을 찾는데 $O(logN)$, 이진 탐색을 할 때 $O(logN)$이 소비되므로 총 $O(log^{2} N)$의 시간 복잡도가 소요된다.

 

이제 머지 소트 트리를 사용하는 문제를 풀러 가보자.

관련 문제

https://www.acmicpc.net/problem/7469

https://www.acmicpc.net/problem/13544