[자료구조 및 알고리즘] 머지소트트리 (merge sort tree)

머지소트트리 (merge sort tree)

머지 소트 트리는 세그먼트 트리의 변형으로, 특정 구간에서 정렬된 데이터를 효율적으로 처리할 수 있는 자료구조이다. 주로 구간 내 특정 값의 개수를 세거나 k번째 작은 수를 찾는 문제 등에 활용된다.

 

1. 머지 소트 트리의 개념

• 머지 소트 트리는 세그먼트 트리와 비슷하지만, 각 노드에 구간에 해당하는 데이터를 정렬된 상태로 저장한다. 
• 세그먼트 트리에서 각 노드가 단일 값을 저장하는 반면, 머지 소트 트리에서는 리스트 또는 배열 형태로 정렬된 값을 저장한다.

2. 머지 소트 트리의 구성

• 리프 노드: 각 배열의 원소를 저장
• 내부 노드: 해당 구간의 두 하위 노드 데이터를 합친 후 정렬한 리스트를 저장

3. 구현 방법

1) 트리 구축

void build(int s, int e, int node) {
	if(s == e) {
    	tree[node] = {a[s]};
    } else {
    	int mid = (s + e) / 2;
        build(s, mid, node * 2);
        build(mid + 1, e, node * 2 + 1);
        merge(
        tree[node * 2].begin(), tree[node * 2].end(),
        tree[node * 2 + 1].begin(), tree[node * 2 + 1].end(),
        back_inserter(tree[node]));
    }
}

// merge는 두 개의 정렬된 범위를 병합하여 하나의 정렬된 범위를 생성한다.

//template<class InputIterator1, class InputIterator2, class OutputIterator>
//OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
//                     InputIterator2 first2, InputIterator2 last2,
//                     OutputIterator result);

// back_inserter는 컨테이너의 끝에 값을 추가하는 반복자 생성

merge 함수 부분은 아래처럼 표현할 수도 있다.

for (int i = MAX_ST / 2 - 1; i > 0; --i) {
    vector<int>& c = arr[i];        // 현재 노드의 벡터
    vector<int>& l = arr[i * 2];   // 왼쪽 자식 노드의 벡터
    vector<int>& r = arr[i * 2 + 1]; // 오른쪽 자식 노드의 벡터

    // 현재 노드 벡터의 크기를 자식 벡터의 크기 합으로 조정
    arr[i].resize(l.size() + r.size());

    for (int j = 0, p = 0, q = 0; j < c.size(); ++j) {
        // 오른쪽 벡터를 모두 사용했거나, 왼쪽 벡터의 값이 더 작을 때
        if (q == r.size() || (p < l.size() && l[p] < r[q])) {
            c[j] = l[p++];  // 왼쪽 벡터의 값을 병합
        } else {
            c[j] = r[q++];  // 오른쪽 벡터의 값을 병합
        }
    }
}

2) 쿼리 처리 (Query)

int query(int s, int e, int l, int r, int node, int x) {
	// 범위를 벗어난 경우
	if(s > r || e < l) return 0;
    if(l <= s && e <= r) {
    	// 현재 구간이 완전히 쿼리에 포함될 때
    	return lower_bound(tree[node].begin(), tree[node].end(), x) - tree[node].begin();
    }
    // 좌우 나눠서 탐색
    int mid = (s + e) / 2;
    return (query(s, mid, l, r, node * 2) + query(mid + 1, e, l, r, node * 2 + 1));
}

머지 소트 트리에서는 구간 내 특정 조건을 만족하는 값의 개수를 구하는 데 유용하다. 이를테면 arr[L...R] 범위에서 값이 x보다 작은 수의 개수를 찾을 때 용이하다.

 

4. 시간 복잡도

• 트리 구축: 각 노드에서 정렬 작업을 수행하며, 트리의 높이가 O(logN)이므로 전체 복잡도는 O(NlogN)
• 쿼리 처리: 각 쿼리에서 O(logN) 높이의 노드를 탐색하고, 각 노드에서 이진 탐색을 수행하므로 O(log^2N)

 

5. 머지 소트 트리의 응용

1. 구간 내 작은 값의 개수 찾기

• 특정 값보다 작은 값, 큰 값, 또는 특정 범위에 속하는 값의 개수를 구할 때 사용

2. k번째 작은 수 찾기

• lower_bound 등을 활용해 구간 내 k번째 작은 값을 효율적으로 찾을 수 있

6. 장점과 단점

• 장점
  • 구간 쿼리에 정렬 정보를 활용하므로, 특정 유형의 문제에서 매우 효율적.
• 단점
  • 공간 복잡도가 O(NlogN)으로 세그먼트 트리보다 크다.
  • 업데이트 작업이 비효율적이어서, 구간 쿼리가 많고 업데이트가 적은 문제에 적합하다.