Mo 알고리즘

모 알고리즘(중국어: 莫隊算法)은 아마도 처음 발견된 것은 아니겠지만, 2000년대 후반 중국의 경쟁 프로그래머 모타오(莫涛)와 그의 팀원들이 대중화한 것은 분명합니다.

이 알고리즘은 가장 발전된 자료구조로도 풀 수 없는 경우가 많은 다양한 부분 구간 쿼리에 오프라인으로 답할 수 있게 해 줍니다.

예를 들어 다음과 같은 문제를 생각해 봅시다. $1$부터 $n$까지의 정수로 이루어진 크기 $n$의 배열이 주어지고, 미리 알려진 $q$개의 질의 “구간 $[l_i, r_i]$에 있는 서로 다른 수의 개수"에 답해야 합니다.

#알고리즘

쿼리에 대한 제곱근 휴리스틱이 쿼리를 시간적 특성에 따라 묶는다면, Mo 알고리즘은 공간적 특성에 따라 묶습니다.

모든 쿼리를 왼쪽 경계를 기준으로 크기 $c \approx \sqrt n$의 블록으로 묶고, 각 블록 안에서는 쿼리를 오른쪽 경계 기준으로 정렬합시다:

// границы и номер запроса, на который нужно ответить
struct query { int l, r, idx; };

int a[maxn], ans[maxq]; // исходный массив и массив ответов на запросы
vector<query> b[c];


// где-то в main:

for (query q : queries)
    b[q.l / c].push_back(q);

for (int i = 0; i < c; i++) {
    sort(b[i].begin(), b[i].end(), [](query a, query b){
        return a.r < b.r;
    });
}

이러한 각 쿼리 블록을 다음 변수들을 두고 개별적으로 처리하겠습니다:

• 현재 구간의 경계 $[l, r]$(초기에는 빈 구간: $l = i \cdot c$, $r = i \cdot c - 1$);
• 크기가 $n$인 배열 cnt. 각 값마다 현재 구간에서 그 값을 가진 원소의 개수를 저장합니다(처음에는 0으로 채워져 있습니다);
• 현재 구간에 있는 서로 다른 원소의 수, 즉 배열 cnt에서 0이 아닌 원소의 수와 같은 변수 res(처음에는 0).

배열 cnt와 변수 res는 경계를 한 칸 넓히거나 좁힐 때 $O(1)$에 쉽게 다시 계산할 수 있습니다:

int cnt[maxn];
int res;

void add(int k) {
    if (cnt[a[k]]++ == 0)
        res++;
}

void del(int k) {
    if (--cnt[a[k]] == 0)
        res--;
}

경계를 왼쪽과 오른쪽으로 천천히 움직여서 현재 구간이 어느 시점에는 각 쿼리 구간과 같아지도록 하고, 그 시점에 res를 답 배열 ans의 해당 칸에 기록하여 쿼리에 답하겠습니다.

구체적으로는, 현재 구간의 오른쪽 경계를 다음 쿼리의 오른쪽 경계와 같아질 때까지 이동시키고(쿼리들은 오른쪽 경계 기준으로 정렬되어 있습니다), 그다음 왼쪽 경계를 해당 쿼리의 왼쪽 경계와 일치할 때까지 오른쪽 또는 왼쪽으로 이동시킵니다:

for (int i = 0; i < c; i++) {
    // обнуляем переменные
    int l = i * c, r = i * c - 1;
    memset(cnt, 0, sizeof cnt);
    res = 0;
    for (query q : b[i]) {
        // пока правая граница не дошла до границы запроса
        while (r < q.r)
            add(++r);
        // дальше делаем так, чтобы левая граница совпала
        while (l < q.l)
            del(l++);
        while (l > q.l)
            add(--l);
        ans[q.idx] = res;
    }
}

요령은 구간들이 정렬되어 있으므로 오른쪽 경계는 전체적으로 $O(n)$만큼 이동하고, 모든 왼쪽 경계가 루트 블록별로 묶여 있으므로 왼쪽 경계는 매번 최대 $O(\sqrt n)$만큼만 이동한다는 점입니다. 모든 블록에 걸쳐 왼쪽 경계를 변경하는 데에는 총 $O(q \sqrt n)$번의 연산이, 오른쪽 경계를 변경하는 데에는 $O(n \sqrt n)$번의 연산이 필요하므로, 최종 시간 복잡도는 $O(q \sqrt n + n \sqrt n)$입니다.

#변형

문제. 구간에서 가장 자주 등장하는 원소를 찾아야 합니다.

마찬가지로 cnt 배열을 유지하면서, 이와 별도로 (등장 횟수, 원소) 쌍을 정렬된 상태로 저장하고 최댓값을 꺼낼 수 있는 보조 내부 자료구조를 함께 관리할 수 있습니다. 이를 위해 set 같은 이진 구조를 사용할 수 있지만, 이렇게 하면 점근적 복잡도에 로그가 추가로 붙습니다.

순수한 $O(n \sqrt n)$에 문제를 풀려면, 내부 구조로 이중 연결 리스트의 배열(원소의 등장 횟수 → 그 등장 횟수를 가진 원소들)과 함께, 각 원소가 현재 어느 리스트의 어느 위치에 있는지를 가리키는 포인터-반복자의 배열을 두면 됩니다. 그러면 원소를 추가 / 삭제할 때는 그 원소를 현재 리스트에서 제거하여 한 단계 위 / 아래 리스트에 삽입하고, 쿼리에 답할 때는 비어 있지 않은 가장 위쪽 리스트에서 아무 원소나 하나 꺼내면 됩니다.

구조를 전혀 사용하지 않고도 풀이를 단순화할 수 있습니다. 배열 cnt와 답 res(가장 많이 등장하는 원소의 등장 횟수)만 유지하되, res는 원소를 추가할 때만 갱신하고 원소를 삭제할 때는 아무것도 하지 않습니다:

void add(int k) {
    res = max(res, ++cnt[a[k]]);
}

void del(int k) {
    cnt[a[k]]--;
    // res тут не обновляется
}

이제 메인 프로시저에서 왼쪽 경계를 되돌릴 때 res도 되돌립니다. 이를 위해서는 쿼리를 처리하기 전(왼쪽 경계를 확장하기 시작하기 전)의 값을 기억해 두기만 하면 됩니다:

for (int i = 0; i < c; i++) {
    int l = i * c, r = i * c - 1;
    memset(cnt, 0, sizeof cnt);
    res = 0;
    for (query q : b[i]) {
        while (r < q.r)
            add(++r);
        int backup = res;
        while (l < q.l)
            del(l++);
        ans[q.idx] = res;
        while (l > q.l)
            add(--l);
        res = backup;
    }
}

문제. 구간에서 $k$번째 순서 통계량을 찾아야 합니다.

쿼리에 포함된 모든 수를 데카르트 트리나 다른 아무 트리 — 예를 들어 합을 위한 세그먼트 트리나 펜윅 트리 — 에 저장해 두고, $O(\log n)$에 그 트리를 갱신하고 트리를 따라 내려가는 탐색을 할 수 있습니다.

로그를 없애기 위해, 의외로 내부 자료구조로 제곱근 분할법을 사용할 수 있습니다. 모든 수를 $1$부터 $n$까지의 범위로 압축하고, “수 $x$가 몇 번 등장하는가"를 나타내는 배열을 만든 뒤 이 배열의 각 제곱근 블록마다 합을 유지해야 합니다. 갱신할 때는 정확히 두 칸에 $\pm 1$을 $O(1)$에 수행하면 되고, $k$번째 순서 통계량을 질의할 때는 먼저 $O(\sqrt n)$개의 블록을 훑은 다음 한 블록 안의 $O(\sqrt n)$개 원소를 훑으면 됩니다.

내부 구조에 대한 갱신 쿼리는 $O(n \sqrt n)$번이고 읽기 쿼리는 $O(n)$번뿐이므로, 후자에 대한 $O(\sqrt n)$의 점근적 복잡도는 아무런 영향을 주지 않습니다. 이는 루트 최적화가 정확히 같은 문제에서 트리를 점근적으로 이기는, 그것도 다른 루트 최적화 내부에서 이기는 꽤 드문 상황입니다.

트리에서. 일부 문제에서는 트리의 경로에 대한 연산 결과를 계산해야 합니다. 예를 들어, 각 정점마다 수가 하나씩 적혀 있고, 경로 위에 있는 서로 다른 값의 개수를 반환해야 하는 경우입니다.

아이디어는 LCA를 RMQ로 환원하는 것과 거의 같습니다. 트리의 오일러 투어(각 정점을 두 번씩)를 적으면 문제는 배열에 대한 문제로 환원되는데, 단 한 가지 예외가 있습니다. 바로 구간에 정확히 1번 포함된 원소만 자료구조에 추가해야 한다는 것입니다.

자세한 내용은 트리 위의 쿼리에 관한 글에서 읽을 수 있습니다.

«3D Мо». 굳이 원한다면 이 방법은 갱신 쿼리를 처리해야 하는 문제에도 적용할 수 있습니다. 이를 위해 get 쿼리에 세 번째 매개변수 $t$를 도입해야 하며, 이 값은 현재 get 이전에 있었던 update 쿼리의 개수(«시간»)와 같습니다.

모든 get-쿼리를 다시 정렬하되, 이번에는 다음 순서로 정렬합니다

같은 알고리즘으로 처리하되, 이번에는 3차원에서 처리합니다.

유일한 차이점은 이제 배열의 버전 사이를 전환할 때 정확히 하나의 원소를 바꿔야 하며, 그 원소가 현재 구간에 속해 있었다면 때때로 자료 구조에서도 그 원소를 바꿔야 한다는 것입니다.

이러한 접근 방식의 시간 복잡도는 $O(n^{\frac{5}{3}})$이며, 이는 원래 알고리즘과 같은 방식으로 증명됩니다.