머지 소트 트리

노드마다 정렬 배열을 든 세그 트리 — 구간 k번째 수.

플래티넘 IV

1강 정렬 배열을 담는 세그먼트 트리 공식

무엇을 해결하나

머지 소트 트리는 "구간 $$[l, r]$$ 안에서 값이 $$k$$ 보다 큰(작은) 원소의 개수",
나아가 "구간 $$[l, r]$$ 의 $$j$$ 번째로 작은 수" 같은 질의를 처리하는 정적 자료
구조다. 배열은 갱신되지 않는다고 가정한다.

핵심 발상은 표준 세그먼트 트리의 각 노드에, 그 노드가 담당하는 구간의 원소들을
정렬한 배열을 통째로 저장하는 것이다. 노드의 정렬 배열은 두 자식의 정렬
배열을 병합(merge)해 만든다 — 그래서 이름이 "머지 소트 트리"다.

         [1,2,3,5,7,8]            (전체)
        /            \
   [2,5,7]          [1,3,8]
   /     \          /     \
[5,2]   [7]      [3,1]   [8]

메모리와 구축

깊이마다 모든 원소가 정확히 한 번씩 나타나므로 한 깊이의 총 크기는 $$N$$ 이고,
깊이가 $O(\log N)$ 이라 전체 메모리는 $O(N \log N)$ 이다. 각 노드 배열을 자식
병합으로 만들면 구축 시간도 $O(N \log N)$ — 사실상 병합 정렬과 같다.

질의: "k보다 큰 원소 개수"

구간 질의 $$[l, r]$$ 은 표준 세그 트리처럼 $O(\log N)$ 개의 노드로 분해된다. 각
노드는 정렬 배열을 들고 있으므로, 이분 탐색으로 그 안에서 $$k$$ 초과 원소
개수를 $O(\log N)$ 에 센다. 분해된 노드가 $O(\log N)$ 개이므로 한 질의는
$O(\log^2 N)$ 이다.

핵심: "구간을 노드로 쪼개기" $O(\log N)$ × "노드 안 이분 탐색" $O(\log N)$
$= O(\log^2 N)$ .

질의: "구간 k번째 수"

값에 대해 한 번 더 이분 탐색을 씌운다. "값 $$x$$ 이하가 구간 안에 몇 개인가"를
위 방법으로 세면서, 그 개수가 $$k$$ 이상이 되는 최소 $$x$$ 를 찾는다. 그러면 한
질의가 $O(\log^3 N)$ 이 되는데, 값을 좌표 압축하고 외부 이분 탐색을 세그 트리
내부 하강과 합치는 분수 캐스케이딩 기법으로 $O(\log^2 N)$ 까지 줄일 수
있다(고급).

다른 풀이와의 비교

구간 k번째 수는 퍼시스턴트 세그먼트 트리로 $O(\log N)$ 에, 오프라인 + Mo's
알고리즘으로도 풀 수 있다. 머지 소트 트리는 구현이 단순하고 "초과/이하 개수"
같은 부등식 카운팅에 특히 직관적이라는 강점이 있다.

2강 구현과 변형 공식

구간 내 k 초과 원소 개수 구현

tree[x]를 정렬된 vector<int>로 둔다. 구축은 재귀로 두 자식을 병합한다.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
vector<int> tree[4 * MAXN];
int arr[MAXN];

void build(int x, int s, int e) {
    if (s == e) { tree[x] = { arr[s] }; return; }
    int m = (s + e) / 2;
    build(x * 2, s, m);
    build(x * 2 + 1, m + 1, e);
    // 두 자식의 정렬 배열을 병합
    merge(tree[x * 2].begin(), tree[x * 2].end(),
          tree[x * 2 + 1].begin(), tree[x * 2 + 1].end(),
          back_inserter(tree[x]));
}

// [l, r]에서 값 > k 인 원소 개수
int query(int x, int s, int e, int l, int r, int k) {
    if (r < s || e < l) return 0;
    if (l <= s && e <= r) {
        // tree[x] 중 k 초과 개수 = 전체 - (k 이하 개수)
        int cnt_le = upper_bound(tree[x].begin(), tree[x].end(), k)
                     - tree[x].begin();
        return (int)tree[x].size() - cnt_le;
    }
    int m = (s + e) / 2;
    return query(x * 2,     s,     m, l, r, k)
         + query(x * 2 + 1, m + 1, e, l, r, k);
}

upper_bound는 $$k$$ 이하의 개수를 주므로, 전체 크기에서 빼면 $$k$$ 초과 개수가
나온다. " $$k$$ 이상 개수"가 필요하면 lower_bound를 쓰면 된다.

흔한 실수

부등호 방향 — lower_bound(처음으로 $\ge k$ ), upper_bound(처음으로
$$> k$$ )의 의미를 정확히 구분하자. "이상/초과/이하/미만" 네 경우를 손으로
확인하는 습관이 필요하다.
메모리 — $O(N \log N)$ 정수가 들어가므로 $$N$$ 이 $$10^5$$ 수준이면 수백만
개다. 노드 배열을 vector로 두되 4 * MAXN 크기 정적 배열이 메모리를 많이
먹는다는 점에 유의한다.
갱신 시도 — 이 구조는 정적이다. 값이 바뀌면 정렬 배열 전체를 다시 만들어야
하므로, 갱신이 필요하면 다른 구조(BIT of 정렬, 분할 평방, 퍼시스턴트 등)를
고려한다.

변형과 응용

질의	방법
구간 내 $$[a, b]$$ 범위 원소 개수	(≤ b 개수) − (< a 개수)
구간 k번째 수	값에 대한 외부 이분 탐색
구간 내 $$k$$ 미만 개수	`lower_bound`

대표 연습 문제로는 BOJ의 "구간 내 k보다 큰 원소 개수", "수열과 쿼리" 계열,
그리고 좌표 압축 후 구간 k번째 수를 묻는 문제들이 있다. 머지 소트 트리를 한 번
구현해 보면 이후 등장하는 분수 캐스케이딩과 웨이블릿 트리의 동기를
훨씬 잘 이해하게 된다.

질의	방법
구간 내 $\([a, b]\)$ 범위 원소 개수	(≤ b 개수) − (< a 개수)
구간 k번째 수	값에 대한 외부 이분 탐색
구간 내 $\(k\)$ 미만 개수	`lower_bound`